121 买卖股票的最佳时机

本文最后更新于:2021年2月25日 中午

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

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

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

示例 1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

Solution

  • 暴力法,超时
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// @lc code=start
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int res=0;
for(int i=0; i<n; ++i){
for(int j=i+1; j<n; ++j)
res = max(res, prices[j]-prices[i]);
}
return res;
}
};
// @lc code=end
  • 贪心算法
  • 假如计划在第 i 天卖出股票,那么最大利润的差值一定是在[0, i-1] 之间选最低点买入;所以遍历数组,依次求每个卖出时机的的最大差值,取最大值。
  • 贪心的想法就是取最左最小值,取最右最大值,那么得到的差值就是最大利润。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// @lc code=start
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int minPrice = 1e9, maxProf = 0;
for(int i : prices){
maxProf = max(maxProf, i-minPrice);
minPrice = min(minPrice, i);
}
return maxProf;
}
};
// @lc code=end

动态规划

参考 @liweiwei1419代码随想录

  • 定义状态
  • 推导状态转移方程
  • 确定初始状态 base case
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if(n<2) return 0;

vector<vector<int>> dp(n, vector<int>(2, 0));
// dp[i][0] 下标为 i 这天结束的时候,不持股,手上拥有的现金数
// dp[i][1] 下标为 i 这天结束的时候,持股,手上拥有的现金数

dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i=1; i<n; ++i){
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]);
dp[i][1] = max(dp[i-1][1], -prices[i]);
}
return dp[n-1][0];
}
};
  • 状态压缩,利用滚动数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(2, vector<int>(2, 0)); // 滚动数组
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1]+prices[i]);
dp[i % 2][1] = max(dp[(i - 1) % 2][1], -prices[i]);
}
return dp[(n - 1) % 2][0];
}
};