121. 买卖股票的最佳时机
一句话套路边走边记历史最低价,当天价减它取最大
题目描述
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
输入:prices = [7,6,4,3,1] 输出:0 解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
提示:
1 <= prices.length <= 1050 <= prices[i] <= 104
思路
时间
O(n)空间
O(1)思路
只许买一次卖一次(先买后卖)。边扫边记「历史最低价」,用当天价格减它取最大 —— 等价于对每个卖出日算最优买入日。
家族
Q122 无限次交易 = 累加所有上涨段;Q123 最多 2 笔 / Q188 最多 k 笔 = 状态机 DP;
Q309 含冷冻期、Q714 含手续费 = 在同一套状态机上改转移。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0121 {
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) return 0; // 防 prices[0] 越界(题面保证 n >= 1)
int ans = 0;
int low = prices[0]; // 到目前为止的最低买入价
for (int p : prices) {
ans = max(ans, p - low); // 今天卖
low = min(low, p); // 更新「今天及之前」最便宜的买点
}
return ans; // 全程下跌时保持 0(不交易)
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0121::Solution s;
vector<int> a{7, 1, 5, 3, 6, 4};
CHECK_EQ(s.maxProfit(a), 5); // 第 2 天 1 买、第 5 天 6 卖
vector<int> b{7, 6, 4, 3, 1};
CHECK_EQ(s.maxProfit(b), 0); // 一直跌就不做
vector<int> c{1, 2};
CHECK_EQ(s.maxProfit(c), 1);
vector<int> d{2, 4, 1}; // 低点出现在高点之后,不能倒着卖
CHECK_EQ(s.maxProfit(d), 2);
vector<int> e{2, 1, 4}; // 卖出日可以比买入日晚很多
CHECK_EQ(s.maxProfit(e), 3);
vector<int> f{5};
CHECK_EQ(s.maxProfit(f), 0);