通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            网站从因情语写改为晴雨            这个网站的模板也从calmlog_ex改为 whimurmur

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

218人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/856

声明:请尊重原作者的劳动,如需转载请注明出处


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

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

示例 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。

难度:中等;标签:动态规划;编程语言:C++


我的解法

int maxProfit(vector<int>& prices) {
        int res = 0;
        stack<int> s;

        for(int i = 0; i < prices.size(); i++){
            if(s.empty() || prices[i] < s.top()){
                s.push(prices[i]);
            }
            if(prices[i] > s.top()){
                res = max(res, prices[i] - s.top());
            }
        }

        return res;
    }

这里用s保存一个递减栈,保存当前最小值(买入价格最低),如果价格上升,就试着卖一下,最后返回卖出价最高的;不好理解,画个图理解一下会好点

如图有5天,s栈顶值,结果如图,在第3,5天价格上升,虽然第4天最小值较小,但由于第3天上升较多,所以在第2天买,第3天卖


其它解法

这里的s可以去掉,因为只要最小的栈顶值,所以有下面的解法

int maxProfit(vector<int>& prices) {
        int cost = INT_MAX, profit = 0;
        for(int price : prices) {
            cost = min(cost, price);
            profit = max(profit, price - cost);
        }
        return profit;
    }

而且把每天的价格变化也省了,因为如果价格下降,相减为负,求max不可能取到负值,不过没有上面的代码,这里更不好理解


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告