剑指 Offer 63. 股票的最大利润

解题思路1：栈

维护一个单调递减栈

假设我们能获取的最大利润为 max

遍历数组 prices

  • 如果当前元素比栈顶元素小则入栈

  • 如果当前元素比栈顶元素大，那么我们就计算 prices[cur] - stack.peek() 与 max 的值，如果 prices[cur] - stack.peek() 比 max 大，就更新最大利润 max

代码

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices.length == 0){
  4.             return 0;
  5.         }
  6.         Stack<Integer> stack = new Stack<>();
  7.         stack.push(prices[0]);
  8.         int max = 0;
  9.         for(int i = 1; i < prices.length; i++){
  10.             if(prices[i] > stack.peek()){
  11.                 max = Math.max(max,prices[i] - stack.peek());
  12.             }else {
  13.                 stack.push(prices[i]);
  14.             }
  15.         }
  16.         return max;
  17.     }
  18. }

复杂度分析

  • 时间复杂度：O(N)

我们从头至尾遍历了一遍 prices 数组，时间复杂度为 O(N)

  • 空间复杂度：O(N)

我们额外申请了一个栈，最坏的情况是 prices 数组单调递减，我们需要存储所有的元素，空间复杂度为 O(N)

解题思路2：动态规划

动态规划的解题步骤：

  1. 状态定义
  2. 确定状态转移方程与初始值
  3. 递推实现

状态定义

声明 dp 数组：dp[i][2]

dp[i][0] 表示第 i 天结束后，当前持股时，持有的最大利润
dp[i][1] 表示第 i 天结束后，当前不持股时，持有的最大利润

确定状态转移方程与初始值

dp[i][0] 表示为第 i 天持有股票时的最大利润

dp[0][0] 为 -prices[0]

dp[i][0] 的情况有两种：

  • 前一天不持股，当天持股
  • 前一天持股，当前什么也不做

状态转移方程为：

  1. dp[i][0] = Math.max(-prices[i],dp[i - 1][0]);

dp[i][1] 表示为第 i 天没有持有股票时的最大利润

dp[0][1] 为 0

dp[i][1] 的情况有两种：

  • 前一天持股，当天卖出
  • 前一天不持股，当天什么也不做

状态转移方程为：

  1. dp[i][1] = Math.max(dp[i - 1][0] + prices[i],dp[i - 1][1]);

返回值：

最后的返回结果必然为不持股的情况，所以返回 dp[prices.length - 1][1]

代码

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices.length == 0){
  4.             return 0;
  5.         }
  6.         int[][] dp = new int[prices.length][2];
  7.         dp[0][0] = -prices[0];
  8.         dp[0][1] = 0;
  9.         for(int i = 1; i < prices.length; i++){
  10.             dp[i][0] = Math.max(-prices[i],dp[i - 1][0]);
  11.             dp[i][1] = Math.max(dp[i - 1][0] + prices[i],dp[i - 1][1]);
  12.         }
  13.         return dp[prices.length - 1][1];
  14.     }
  15. }

复杂度分析

  • 时间复杂度：O(N)

我们需要从头至尾遍历 prices 数组，所以时间复杂度为 O(N)

  • 空间复杂度：O(N)

额外开辟了 dp 数组，占用了 O(N) 的空间