题目

思路

一句话：枚举每一天作为卖出日，它的最佳买入日就是「之前所有天里价格最低的那天」。

先想最直白的做法：枚举买入日 i，再枚举卖出日 j（j > i），记录所有 prices[j] - prices[i] 的最大值。这个思路完全正确，但时间是 O(n²)；当 n = 105 时约要 1010 次比较，会超时。

关键观察：当卖出日固定时，前面的所有买入候选里，只需要知道价格最低的那一个；其他更贵的买入价都不可能产生更大的利润。所以二重循环可以拆成一次扫描：从左到右一边维护「历史最低价」lowest，一边用当前价格减它来更新答案。

这也是它被归到 Sliding Window 的原因：候选买入日是窗口左端，当前卖出日是窗口右端；窗口左端始终停在历史最低价，一旦遇到更低的价格，就把左端拉到当前位置。

以 [4, 7, 1, 5] 为例：