171 lines
5.0 KiB
Markdown
171 lines
5.0 KiB
Markdown
---
|
||
tags: [贪心算法, 数组, 动态规划, 简单, LeetCode]
|
||
create time: 2026-05-16 10:00
|
||
---
|
||
|
||
# 77 - 买卖股票的最佳时机
|
||
|
||
> [!question] 一句话描述
|
||
> 给定每天的价格，**只能完成一笔交易**（买一次 + 卖一次），求最大利润。
|
||
|
||
## 题面
|
||
|
||
| 要素 | 描述 |
|
||
|------|------|
|
||
| **输入** | `prices` int 数组，第 `i` 个元素表示第 `i` 天的价格 |
|
||
| **约束** | 先买入、后卖出，不能在同一天；若无利润返回 `0` |
|
||
| **输出** | 最大利润（int） |
|
||
| **数据范围** | `1 <= prices.length <= 10^5`，`0 <= prices[i] <= 10^4` |
|
||
|
||
### 示例 1
|
||
|
||
```
|
||
输入: [7,1,5,3,6,4]
|
||
输出: 5
|
||
解释: 第 2 天以 1 买入，第 5 天以 6 卖出 → 6 - 1 = 5
|
||
```
|
||
|
||
### 示例 2
|
||
|
||
```
|
||
输入: [7,6,4,3,1]
|
||
输出: 0
|
||
解释: 价格持续下跌，无法获利
|
||
```
|
||
|
||
## 思路
|
||
|
||
> [!tip] 核心洞察：不要「预测」最高点，而是「跟踪」最低点
|
||
|
||
暴力做法是枚举每一对 `(买入日, 卖出日)`，复杂度 O(n²)，在 `n = 10^5` 时必然超时。我们需要一个 **遍历一次就能得出答案** 的方法。
|
||
|
||
关键问题：**对于每个「今天」，最优的买入价是什么？**
|
||
|
||
答案是：从第 0 天到今天为止的**最小价格**。
|
||
|
||
换句话说，我们不用提前知道未来的最低价——随着遍历推进，维护两个变量就够了：
|
||
|
||
- `minPrice` —— 到目前为止见过的最低价格
|
||
- `maxProfit` —— 用这个最低价格买入、在今天卖出的最大利润
|
||
|
||
每一步做一次比较：如果 `prices[i] - minPrice > maxProfit`，就更新利润；否则继续前进。
|
||
|
||
整个过程可以理解为一条从左到右的扫描线：
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["📍 扫描线"] -->|"遍历每一天"| B["看到当前价格"]
|
||
B --> C{"比历史最低价还低？"}
|
||
C -->|"是"| D["更新 minPrice"]
|
||
C -->|"否"| E["检查利润"]
|
||
D --> E
|
||
E --> F{"当前利润更高？"}
|
||
F -->|"是"| G["更新 maxProfit"]
|
||
F -->|"否"| H["继续往后走"]
|
||
G --> H
|
||
H -->|"还没到最后"| A
|
||
H -->|"到达末尾"| I["返回 maxProfit"]
|
||
```
|
||
|
||
**为什么这是正确的？** 因为最优解一定形如「在某一天以最低买入价购入，在之后以最高价卖出」。当我们的扫描线走到真正的"卖出日"时，`minPrice` 已经记录了它之前的最低买入价，此时计算出的利润恰好就是答案。
|
||
|
||
### 一步步执行演示
|
||
|
||
以 `[7,1,5,3,6,4]` 为例，追踪两个变量的变化：
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
subgraph Step0 ["初始状态"]
|
||
S0["minPrice = ∞\nmaxProfit = 0"]
|
||
end
|
||
subgraph Step1 ["Day 0: price = 7"]
|
||
S1["minPrice = 7\nmaxProfit = 0"]
|
||
end
|
||
subgraph Step2 ["Day 1: price = 1"]
|
||
S2["minPrice = 1 ← 更新低价\nmaxProfit = 0"]
|
||
end
|
||
subgraph Step3 ["Day 2: price = 5"]
|
||
S3["minPrice = 1\nmaxProfit = 4 ← 更新利润"]
|
||
end
|
||
subgraph Step4 ["Day 3: price = 3"]
|
||
S4["minPrice = 1\nmaxProfit = 4"]
|
||
end
|
||
subgraph Step5 ["Day 4: price = 6"]
|
||
S5["minPrice = 1\nmaxProfit = 5 ← 更新利润 ← 最终答案"]
|
||
end
|
||
subgraph Step6 ["Day 5: price = 4"]
|
||
S6["minPrice = 1\nmaxProfit = 5"]
|
||
end
|
||
S0 --> S1 --> S2 --> S3 --> S4 --> S5 --> S6
|
||
```
|
||
|
||
## 代码提示
|
||
|
||
```
|
||
// 初始化
|
||
minPrice = 最大值（或第一天的价格）
|
||
maxProfit = 0
|
||
|
||
// 对每一天 i 从 1 开始遍历
|
||
if prices[i] < minPrice:
|
||
minPrice = prices[i]
|
||
else if prices[i] - minPrice > maxProfit:
|
||
maxProfit = prices[i] - minPrice
|
||
|
||
return maxProfit
|
||
```
|
||
|
||
> [!danger] 常见陷阱：空数组
|
||
> 题目保证 `prices.length >= 1`，但实战中应先判断边界条件再访问 `prices[0]`。
|
||
|
||
## 技巧
|
||
|
||
| 技巧 | 说明 |
|
||
|------|------|
|
||
| **「今天卖」思维** | 把问题拆成 N 个子问题：假设必须在第 `i` 天卖出，最佳利润是多少？最后取 max 即可 |
|
||
| **只卖不买** | 实际上只需要维护「卖出」的视角——每次考虑「今天卖 vs 之前卖」的最大值，买入隐含在 `minPrice` 中 |
|
||
| **DP 视角** | 这道题也可以写成最简动态规划（状态转移只有两行），后续「买卖股票 II/III」会在此基础上扩展 |
|
||
|
||
## 代码
|
||
|
||
```go
|
||
package main
|
||
|
||
import "fmt"
|
||
|
||
// maxProfit 计算只能进行一次交易时的最大利润
|
||
// 使用一次扫描法：遍历时记录历史最低价和最大利润
|
||
func maxProfit(prices []int) int {
|
||
// 初始化：第 0 天作为参考基准
|
||
minPrice := prices[0]
|
||
maxProfit := 0
|
||
|
||
// 从第 1 天起，逐天判断
|
||
for i := 1; i < len(prices); i++ {
|
||
if prices[i] < minPrice {
|
||
// 发现了更低的价位：刷新买入参考价
|
||
minPrice = prices[i]
|
||
} else if prices[i]-minPrice > maxProfit {
|
||
// 今天的售价能带来更高的利润：记录之
|
||
maxProfit = prices[i] - minPrice
|
||
}
|
||
}
|
||
|
||
return maxProfit
|
||
}
|
||
|
||
func main() {
|
||
// 示例 1
|
||
fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4})) // 5
|
||
// 示例 2
|
||
fmt.Println(maxProfit([]int{7, 6, 4, 3, 1})) // 0
|
||
}
|
||
```
|
||
|
||
### 复杂度分析
|
||
|
||
| 指标 | 结果 |
|
||
|------|------|
|
||
| **时间** | O(n) — 仅一次线性扫描 |
|
||
| **空间** | O(1) — 仅两个整型变量 |
|