Leetcode 121. Best Time to Buy and Sell Stock 最佳股票售卖时(动态规划,数组,模拟)

题目描述

已知一个数组,第i个元素表示第i天股票的价格,你只能进行一次交易(买卖各一次),设计算法找出最大收益

测试样例

Input: [7, 1, 5, 3, 6, 4]
Output: 5
最大收益 = 6-1 = 5 (不是7-1 = 6,因为先买后卖,7买,1买亏了6)


Input: [7, 6, 4, 3, 1]
Output: 0
最大收益为0

详细分析

初看非常简单,遍历数组,每次选择一个元素,找到这个元素后面的数组的最大值,计算差值,和当前最大收益比较即可,就像这样: [7,1,5,3,6,4] 当前7,后面最大6,收益-1 [7,1,5,3,6,4] 当前1,后面最大6,收益5 [7,1,5,3,6,4] 当前5,后面最大6,收益1 如此继续找到即可。 不过这种方法会超时,稍微改变一下,现在不止保持最大收益,还保存最低价格,如果当天价格更低,就刷新最小价格(买),同时如果当天价格减去最小价格的收益最大,就刷新最大价格(卖),过程如下:

[7,1,5,3,6,4] minPrice=INT_MAX,maxProfit=0 => minPrice=7,maxProfit=0

[7,1,5,3,6,4] minPrice=7,maxProfit=0 => minPrice=1,maxProfit=0

[7,1,5,3,6,4] minPrice=1,maxProfit=0 => minPrice=1,maxProfit=4

[7,1,5,3,6,4] minPrice=1,maxProfit=4 => minPrice=1,maxProfit=4

[7,1,5,3,6,4] minPrice=1,maxProfit=4 => minPrice=1,maxProfit=5

[7,1,5,3,6,4] minPrice=1,maxProfit=5 => minPrice=1,maxProfit=5

算法实现

  • 方法1:Time Limit Exceeded
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for(auto start=prices.begin();start!=prices.end();start++){
            int buy = *start;
            int sell = *std::max_element(start,prices.end());
            if((sell - buy)>profit){
                profit = sell-buy;
            }
        }
        return profit;
    }
};
  • 方法2: Accepted
class Solution{
public:
    int maxProfit(vector<int> &prices){
        int profit = 0;
        int minBuy = std::numeric_limits<int>::max();
        for(int i=0;i<prices.size();i++){
            //buy it if current price is less than minimum prices yet
            if(prices[i]<minBuy){
                minBuy = prices[i];
            }
            //sell it if current profit got optimally
            if((prices[i]-minBuy)>profit){
                profit = prices[i]-minBuy;
            }
        }
        return profit;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据和云计算技术

Go语言入门

最近准备学点新东西,聊聊Go语言入门。 Go是google 09年推出的编程语言,Go语言专门针对多处理器系统应用程序的编程进行了优化,使用Go编译的程序可以媲...

38350
来自专栏逸鹏说道

重温数据结构系列随笔:数据结构的基本概念

现在项目已经踏上正轨,有不少时间可以用来学习,昨晚发现柜子里那本大学时候啃过无数遍的(数据结构 C语言版),那真的无限感叹啊,初恋女友啊,大学回忆啊都涌上心头。...

30040
来自专栏take time, save time

[细节决定B度]之二分搜索也不易啊

     实事求是的说二分搜索是我学习算法的时候学的最好,理解的最透彻,能够当时就写出代码的的算法。事到如今,就如我可以分分钟写出hello world一样,我...

31960
来自专栏Pythonista

面向对象的软件开发

很多人在学完了python的class机制之后,遇到一个生产中的问题,还是会懵逼,这其实太正常了,因为任何程序的开发都是先设计后编程,python的class机...

13520
来自专栏数据结构与算法

HDU 2089 不要62

不要62 Problem Description 杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。 杭州交通管理局经常会扩充一些的士车牌照,新近出来一个...

298100
来自专栏Alan's Lab

JS 变量提升

问到 JS 一些细节问题的时候发挥比较糟糕,有些是知道反应得太慢,有些是压根没接触过,还是积累的太少了。这篇的 JS 变量提升问题就是从没有接触过的,网上一搜一...

32020
来自专栏IT大咖说

前端专家聊JS语言家族新成员——R&B

摘要 相信大家对以CoffeeScript、TypeScript为代表的编译到JavaScript的语言已经不陌生。本次分享将介绍 JS 平台语言家族的重要新成...

42580
来自专栏编程之旅

使用Block提高代码可读性

最近一直在思考并持续的扩充着自己的技术栈,比如每天坚持着学习前端知识,并且时常想着在移动端这条路上,自己的技术盲区。诚然,想要在一个领域达到一定的技术高度是挺困...

12030
来自专栏IT派

Python学习路线图

Python上手很容易, 基本有其他语言编程经验的人可以在1周内学会Python最基本的内容.

51400
来自专栏斑斓

高质量代码的特征

回想起来,我觉得我们似乎在误读Uncle Bob的Clean Code,至少我们错误地将所谓Clean与可读性代码简单地划上了等号。尤为不幸的是,在Clean ...

37950

扫码关注云+社区

领取腾讯云代金券