来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

1 题目简介

给定一个数组,它的第  i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意:你不能在买入股票前卖出股票。

输入例子: [7,1,5,3,6,4]。这个例子中第 2 天买入,第 5 天卖出,收益最大为 5。

2 最简单的思路:暴力,但超时

即将所有的情况进行进行遍历,然后维护一个最大收益值。

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

但是此方法的时间复杂度为 O(n^2)。此代码将会超时。

3 解决方式一:单调栈

3.1 什么是单调栈?

单调栈,就是栈内元素单调递增或单调递减的栈。只对栈顶进行操作。比如,一个栈从栈底到栈顶依次存储的[1 3 5 9],则该栈是一个单调递增的栈;反之,一个栈从栈底到栈顶依次存储的[9 5 3 1],则该栈是一个单调递减的栈。

3.2 为什么这道题可以用单调栈来做?

关键点:股票要有收益,卖出的价格一定要高于买入的价格。

因此,对于单调栈,栈底元素是最小的,可以当做买入的价格,而栈顶元素是最大的,当栈顶元素弹出的时候,可以当做卖出的价格(模拟卖出)。因此,弹栈的时候,要维护一个最大收益值(栈顶减去栈顶即可)。

整体思路

(1)判断栈是否为空,如果为空,则返回 0。

(2)对于第一个元素,直接入栈。

(3)对于之后的元素,与栈顶元素进行比较。如果当前元素大于等于栈顶元素,则直接入栈。如果小于栈顶元素,则弹出栈顶,同时计算收益,维护最大收益值;直到当前元素大于栈顶元素,则入栈。

(4)遍历完所有元素后,输出最大收益值。

3.3 模拟过程

以题目中的数据为例子:[7,1,5,3,6,4]

(1)定义一个空的单调栈,一个最大的收益值 max_p=0。

(2)第一个元素为 7,此时栈为空,直接入栈。单调栈=[7]

(3)第二个元素为 1,小于栈顶元素 7,则将栈顶元素 7 弹出栈。弹出之前,栈顶减去栈底为 0,此时 max_p=0。单调栈=[1]

(4)第三个元素为 5,大于等于栈顶元素为 1。因此直接入栈。单调栈=[1,5]

(5)第四个元素为 3,小于栈顶元素 5,则需要将元素 5 弹栈。弹出之前,栈顶减去栈底为 4,4 大于之前的 max_p,因此 max_p 更新为 4。弹出 5 元素后,栈顶为 1,因此将元素 3 压入。单调栈=[1,3]

(6)第五个元素为 6,6 大于栈顶元素 3,直接压入栈。单调栈=[1,3,6]

(7)第六个元素为 4,4 小于栈顶元素 6,则需要弹栈。弹出之前,栈顶减去栈底为 5,5 大于之前的 max_p=4,因此 max_p 更新为 5。弹出 6 元素后,栈顶为 3,4 小于 3,因此将元素 4 压入。单调栈=[1,3,4]

(8)此时所以元素已经遍历完,此时 max_p=5。将 5 结果输出即可。

疑问:有什么遗漏的点么?

如果数据是[1,3,4],则根据模拟流程,三个元素将依次被压入栈,max_p 将不会被更新。

此时,正确的答案应该是 3,而我们得到的结果为 0。

因此,需要加一个哨兵元素。在股票价格的容器的末尾加一个哨兵元素(例如,可以为-1)。使得数据变为[1,3,4,-1]。加上哨兵元素后,遍历到哨兵元素后,需要一次将 4,3,1 弹栈,则 max_p 会被更新,最后得到正确的结果。

3.4 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 如果容器大小为0,则返回0
        if(prices.size() == 0)
            return 0;
        vector<int> v;
        v.push_back(prices[0]);
        // max_p 为最大的收益
        int max_p = 0;
        //哨兵 -1
        prices.push_back(-1);
        for(int j=1; j<prices.size(); j++)
        {
            // 如果当前值大于等于栈顶,则入栈
            if(prices[j]>=v.back())
                v.push_back(prices[j]);
            // 如果当前值小于栈顶,则循环弹栈,直到栈顶小于当前值
            else
            {
                // 记录当前最大收益,记录完后才能弹栈
                max_p = max(max_p, v.back()-v.front());
                while(v.size()>0)
                {
                    if(prices[j]<v.back())
                        v.pop_back();
                    else
                        break;
                }
                // 将当前值入栈
                v.push_back(prices[j]);
            }
        }
        return max_p;
    }
};

此方法的时间复杂度为 O(n)

4 解决方式二:动态规划(dp)

4.1 动态规划解题步骤

很明显,这是一个一维的动态规划。

(1)明确 dp[i],dp[i] 应该表示什么。

(2)根据 dp(i) 和 dp(i-1) 的关系得出状态转移方程。
(3)确定初始值。

4.2 解题过程

根据 4.1 的分析,dp[i]表示前 i 天的最大收入。

确定 dp[i]与 dp[i-1]的关系:如果第 i 天卖出了股票,则收入为(prices[i]-minprice),如果第 i 天没有卖出股票,则收入为 prices[i-1]。因此取这两者的最大值,即为 dp[i]的值。
即:dp[i]=max(dp[i−1],prices[i]−minprice)
其中,minprice 为前 i 天股票的最低价。

初始值:dp[0]=0。

4.3 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0) return 0;
        vector<int> dp (n,0);
        int minprice = prices[0];

        for(int i=1;i<n;i++)
        {
            if(prices[i]<minprice)
                minprice = prices[i];
            dp[i] = max(dp[i-1], prices[i]-minprice);
        }
        return dp[n-1];
    }

};

此方法的时间复杂度为 O(n)

5 代码可不可以更加简化?

官方代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minprice = int(1e9);
        int maxprofit = 0;
        for (auto price : prices){
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(minprice, price);
        }
        return maxprofit;
    }
};

可以看到,官方代码的思路其实是从动态规划的思想中过来的。思想是一致的。

0
Posted in 努力扣代码


Leave a Comment:

电子邮件地址不会被公开。