HHot 100C++ 图解

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 <= 105
  • 0 <= prices[i] <= 104

思路

时间O(n)
空间O(1)

思路

只许买一次卖一次(先买后卖)。边扫边记「历史最低价」,用当天价格减它取最大 —— 等价于对每个卖出日算最优买入日。

家族

Q122 无限次交易 = 累加所有上涨段;Q123 最多 2 笔 / Q188 最多 k 笔 = 状态机 DP;

Q309 含冷冻期、Q714 含手续费 = 在同一套状态机上改转移。

图解

7 0 1 1 5 2 3 3 6 4 4 5
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/14_greedy.cpp15 行
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(不交易)
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q121_best_time_to_buy_and_sell13 行
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);

↑↓ 选择↵ 打开/ 随时唤起