LeetCode121. 买卖股票的最佳时机（单调栈+动态规划）

题目链接：Leetcode121

思路：

1，找前面和它比最小的更新答案，可以维护一个单调栈解决，每次跟栈底比（实际上是单调队列，但不用控制窗口大小就是了）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0; 
        int stk[n], top = -1;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            while (top!=-1 && stk[top]>=prices[i]) top--; //模拟一个单调栈
            stk[++top]=prices[i];
            ans=max(ans, stk[top]-stk[0]);
        }
        return ans;
    }
};

2，动态规划，dp[i]表示到达i时最小的数，每次更新答案时与dp[i-1]求差值就好了

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0; 
        int bef; //int dp[n];
        int ans = 0;
        bef=prices[0]; //dp[0]=prices[0]; //初试状态
        for (int i = 1; i < n; i++) {
            /*
            dp[i]=min(dp[i-1], prices[i]);
            ans=max(ans, prices[i]-dp[i-1]); //在正数内所以不存在溢出的情况，因为负数比正数多一位
            */
            ans=max(ans, prices[i]-bef);
            bef=min(bef, prices[i]);
        }
        return ans;
    }
};

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/calculate23/article/details/100561441
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-03-01 21:44:28
阅读 ( 1199 )
分类：算法

LeetCode121. 买卖股票的最佳时机（单调栈+动态规划）

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看