LeetCode—— 买卖股票的最佳时机

题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），
设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

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

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

一、CPP

1. 动态规划法：

解题思路:利用原问题与子问题的关系，将其变成 大问题的解 = 小问题的解的函数， 从而将问题变成size的扩展即可，当size到达最大后，原问题解决了。(参考原评论)

• DP的keypoint
  转移方程（大问题与小问题的关系）
  1）定义状态：定义一个状态，例如f(i) = 到a[i]为止到最小值
  2）设计转移方程：根据如上状态方程定义，则有 f(i+1) = min(f(i), a[i+1])

• tip:
  转移方程的设计完全依赖于状态的定义，并不是什么样的状态定义，都能有状态转移方程，因此，状态定义决定了该DP方法能否实现
  初始条件的设置： Dp本质还是迭代，总要有一个迭代的初值。

特殊处理小size的问题：有些情况，由于size太小，没法带入转移方程中。

根据该问题，依次回答上述问题：

• 大问题与小问题的关系
  1）状态定义：我们定义max_profit为第i天的最大收益
  2）状态转移方程：
  第i天的最大收益和第i-1天的最大收益之间的关系：
  i) 最大收益不是第i天抛出的， ——> 最大收益和第i天的价格无关
  ii）最大收益是在第i-1天前某天买入的，并在第i天抛出的， ——>与第i天的价格有关

因此第i天的最大收益等于：第i天抛出所造成的最大收益 和 第i-1天之前的最大收益 中的最大值
即：
前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
其中：
前i-1天中的最小价格需时时更新并记录

• 初始条件：
  min 和 max_profit
  min可以等于第一天的price
  max_profit可以等于0， 因为最大收益的最小值就是0， 用人话叫，最低也不能赔了
• 小于最小问题的特殊情况： 当list的长度为0 和 1 时， 没有办法带入转移公式中，需要特殊处理。

时间复杂度:O(n)。
空间复杂度:O(1)。

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        //特殊情况
        if(prices.size()<=1){
            return 0;
        }

        int res = 0;
        int buy = prices[0];
        
        for (int i = 1; i<prices.size(); i++) {
            buy = min(buy, prices[i]);
            res = max(res, prices[i] - buy);
        }
        return res;
    }
};

2. 一次遍历法（DP另一种解释）：

解题思路:用一个变量记录遍历过的数中的最小值，然后每次计算当前值和这个最小值之间的差值最为利润，然后每次选较大的利润来更新。当遍历完成后当前利润即为所求。例如[7,2,5,3,10,1,6,4]，遍历到元素10时，res=8，遍历到1后，buy=1，但是后面的price-buy<res，不会更新res。
时间复杂度:O(n)。
空间复杂度:O(1)。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0, buy = INT_MAX;
        for (int price : prices) {
            buy = min(buy, price);
            res = max(res, price - buy);
        }
        return res;
    }
};

3. 暴力算法：

解题思路:根据题目的要求可以看出，出售的价格要在买入的之后，所以暴力法设置两个索引，sell负责遍历数组，寻找最大值（此最大值也必须在最小值之后，即售出在买入之后），buy必须在sell之后，不断根据sell更新寻找范围寻找最小值。设置result是为了避免出现“局部最优差价”。即当序列为[4,11,2,3,1,10]时，根据前面的思想，sell会一直停留在11处，这导致buy也只能在4和11之间取，最后结果为7。但是后面还有更优的结果：10-1=9。所以设置result，求完result之后更新sell，不让其一直待在“局部”。然后更新最优result值。初始值sell=1，buy=0。为了保证sell在buy之后。
时间复杂度:O(n²)。
空间复杂度:O(1)。

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int buy = 0;
        int sell = 1;
        int result = 0;

        for(int i=1;i<prices.size();i++){
            if(prices[i]>=prices[sell]){
                sell = i;
                for(int j=0;j<=sell;j++){
                    if(prices[j]<prices[buy]){
                        buy = j;
                    }
                }
                if(prices[sell]-prices[buy]>result){
                    result = prices[sell]-prices[buy];
                }
                sell++;
            }
        }
        return result;        
    }
};

二、Java（一次遍历法）

class Solution {
    public int maxProfit(int[] prices) {

        int buy = Integer.MAX_VALUE;
        int res = 0;
        for(int price : prices){
            buy = Math.min(buy,price);
            res = Math.max(res, price - buy);
        }
        return res;        
    }
}

三、Python（一次遍历法）

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # 无穷大的表示
        buy = float("inf")
        res = 0

        for price in prices:
            buy = min(buy, price)
            res = max(res, price - buy)
        return res

四、各语言及算法时间复杂度