题解 | #买卖股票的最好时机#

买卖股票的最好时机

http://www.nowcoder.com/practice/64b4262d4e6d4f6181cd45446a5821ec

这个题目我一开始的想法是,找数组中的最大值,记录该最大值的下标,然后在该下标之前的数据中找最小值,最大值与最小值的差值,就是获得的最大收益,返回这个差值即可。
但是这个想法存在以下问题:
(1)最大值出现在第0天,之后递减,例如[4,2,1]
(2)最大值出现在第0天,之后有次大值,在最大值和次大值之间有最小值,例如[4,1,2]
仅仅是靠上述想法,是不能在这两种情况下正确输出结果的。于是在看了其他人的题解、讨论之后,我发现我还存在一定的理解误区:只有买入了股票才能卖出,这句话我一开始理解的是如果以第i天的价格卖出,那么就要以第i-1天以及之前的价格买,但是显然还有一种情况那就是当天买当天卖,这种情况就比较适用于解决上面提到的问题(1)。但是对于问题(2),还是没有解决,所以可以看到我之前的想法有问题。
于是可以这样考虑,只要在当天之前,以最便宜的价格买入即可。但是这个挑选最便宜的过程,不是像之前一样寻找,而是从第0天开始,假定该价格为买入的价格,然后每次以该价格与当天价格对比,哪个小就把哪个重新记为买入价格,并且计算当前价格与买入价格的差值(也就是收益),并将收益和初始定义的收益比较取最大值,重新赋给收益变量,这样就可以保证该收益变量里的值永远都是卖出当天价格值减去当天之前最便宜买入价格的差值,也就是所求的最大收益。(注:将初始定义的收益定义成0,就可以保证问题(1)的错误不会发生)
代码如下

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int len = prices.size();
        int buy = prices[0];//表示第i天卖出时的买入价格
        int dp = 0;//表示收益
        for(int i = 0; i < len; i++)
        {
            buy = min(buy,prices[i]);
            dp=max(dp,prices[i]-buy);
        }
        return dp;
    }
};
牛客刷题记录 文章被收录于专栏

记录自己的刷题记录,刷过的题的解法

全部评论

相关推荐

05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
点赞 评论 收藏
分享
有担当的灰太狼又在摸鱼:零帧起手查看图片
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务