leetcode 121 买卖股票的最佳时机

深藏阁楼爱情的钟 2022-08-28 03:44 180阅读 0赞

## 前言 ##

题目：[121. 买卖股票的最佳时机][121.]

参考题解：[买卖股票的最佳时机-代码随想录][-]

--------------------

## 提交代码 ##

### 暴力遍历 ###

一道简单题，直接暴力。结果还超时了。怕不是个小袋子。

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int max_profit = 0;
            for(int i=0; i<prices.size()-1; i++){
                for(int j=i+1; j<prices.size(); j++)
                    if(prices[j]>prices[i])
                        max_profit = max(max_profit,prices[j]-prices[i]);
            }
            return max_profit;
        }
    };

### 贪心 ###

没辙了，去看看参考题解。参考题解使用了贪心。

思路：维护一个最小值，维护一个最大上升值。注意，全局最小值的地方，不一定是获取上升最大值的地方。维护的最小值，服务于产生较大值。不同的较大值的比较，诞生最大上升值。(因为随着向后移动，最小值更小的同时，最大值也可能更小。)

这个思路稍微有点难以理解。没明白的话，多看两遍。

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            // 维护一个最小值；维护一个最大上升
            // 注意：最大上升，不一定是在最小值时求得；
            int low = INT_MAX;
            int max_profit = 0;
            for(int i=0; i<prices.size(); i++){
                low = min(low,prices[i]);
                if(low != prices[i])
                    max_profit = max(max_profit,prices[i]-low);
            }
            return max_profit;
        }
    };

### 动态规划 ###

参考题解还提供了一种动态规划的题解。我们需要先看明白它的递推公式。递推公式的本质，是上面贪心的思路。我修改了参考题解的动态规划公式，使其更直观的使用动态规划，表示贪心思路。

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            // 动态规划：
            // dp[i][0] 表示第i天持有股票所得最多现金(继续持有原来股票，买入新股票)，dp[i][0] = max(dp[i - 1][0], -prices[i]);
            // dp[i][1] 表示第i天不持有股票所得最多现金(继续保持手上没有股票,原来手上有股票卖出)，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])
            // 本质(和贪心相同)：dp[i][0]维护一个最小股票值；dp[i][1]维护一个最大的上升。
    
            // 所以我们修改下递推公式
            // 维护一个最小股票值：dp[i][0] = min(dp[i-1][0],prices[i]);
            // 维护一个最大上升：dp[i][1] = max(dp[i-1][1],prices[i]-dp[i][0])
            int len = prices.size();
            if(len == 0) return 0;
            vector<vector<int>> dp(len,vector<int>(2,0));
            dp[0][0] = prices[0];
            dp[0][1] = 0;
            for(int i=1; i<len; i++){
                dp[i][0] = min(dp[i-1][0],prices[i]);
                dp[i][1] = max(dp[i-1][1],prices[i]-dp[i][0]);
            }
    
            return dp[len-1][1];
        }
    };

[121.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.md