leetcode-go/贪心算法/77-买卖股票的最佳时机.md

---
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) — 仅两个整型变量 |