来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
Contents
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;
}
};
可以看到,官方代码的思路其实是从动态规划的思想中过来的。思想是一致的。