题目信息

题目地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1
2
1 <= prices.length <= 105
0 <= prices[i] <= 104

解法一：暴力解法

这题的话暴力解法应该是每个小伙伴一看到题就想到的解法，这里也不例外先写个暴力解法。也就是穷举所有组合的收益再找最大

举个例子：[7,1,5,3,6,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
7 -> 1 = -6
7 -> 5 = -2
7 -> 3 = -4
7 -> 6 = -1
7 -> 4 = -3
1 -> 5 = +4
1 -> 3 = +2
1 -> 6 = +5
1 -> 4 = +3
5 -> 3 = -2
5 -> 6 = +1
5 -> 4 = -1
3 -> 6 = +3
3 -> 4 = +1
6 -> 4 = -2

穷举所有的买卖组合后，最大收益是+5

实现步骤：

第一是扫描全部组合

第二是记录max

第三返回最终max

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
public int maxProfit(int prices[]) {
    int max = 0;
    for(int i = 0; i < prices.length-1; i++){
        for(int j = i+1; j < prices.length; j++){
            int income = prices[j] - prices[i];
            if(income > max){
                max = income;
            }
        }
    }
    return max;
}

外循环是n-1次,内循环是(n-1、n-2、….1) 总共是$\frac{n^2}{2}$次时间复杂度为O(n^2)

空间仅仅使用了两变量因此是O(1)

解法二：动态规划

上个解法时间复杂度太高，在LeetCode种测试也是超时的。作为一个动态规划合集的题那我们肯定是要用动态规划来解一解。

我们怎样去思考：

i天的最终最高收益可以怎样去划分呢？

  1. 它可能就是前i-1天的最高收益是不变的
1
2
3
[4,2,1,5,4]
这5天最高收益是第三天买第四天卖最高为4
也就是前4天的最高的组合。
  1. 它也可能变化比前i-1天的最高收益多
1
2
3
[4,2,1,5,7]
这5天的前4天最高收益是4
算上第5天的话就应该是6

所以这里我们可以清楚它无非两种情况取最大

前i天的最大收益 = max(前i-1天的最大收益，第i天的价格-前i-1天中的最小价格)

这里要迭代要存储的值不仅仅有收益结果还有最小值因此自底向上更好些。每后往遍历一个进来就判断max是不变还是有更大（记录下当前最小值以及当前的结果）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
public int maxProfit(int[] prices) {
    if(prices.length < 2){
        return 0;
    }
    int min = prices[0];
    int max = 0;
    for(int i = 1; i < prices.length; i++) {
        max = max > (prices[i] - min) ? max : prices[i] - min;
        min = min < prices[i] ? min : prices[i];
    }
    return max;
}

比起自底向上来说，自顶向下会麻烦一些。但思路是一样的。这里画个图

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maxProfit(int[] prices) {
    return recurrent(prices,prices.length-1);
}
int recurrent(int[] nums,int index){
    if(index == 0){
        return 0;
    }
    int right = nums[index] - min(nums,index);
    int left = recurrent(nums,--index);
    if(left > right){
        return left;
    }
    return right;
}
int min(int[] nums,int index){
    int min = nums[0];
    for(int i = 1; i < index; i++){
        if(nums[i] < min){
            min = nums[i];
        }
    }
    return min;
}

它的迭代深度是n,但是旁边都有一个找最小也是n所以时间复杂度O($n^2$),如果找最小也是用递归的话就差不多是O($2^n$)。不过即使是n的二次方也是从超时的和暴力一样复杂度。


归根到底还是因为只进行了迭代的思路没进行记录。这边因为递归部分就是线性的所以没有多余的，主要就是最小值那边平均每个进行n/2次。所以是可以记录一下的如果当前索引的值不是之前那个最小值。说明剩下的数列最小值还在里面还是之前那个不用重新遍历。总体上还是复杂度还是不行的。

总结

今日这题的话还是比较好做的，有点不同的是迭代的结构不是同一种类型。动态规划的题自顶向下与自底向上两个方向每题都可进行同时练习。