买卖股票的最佳时机

怎样从“prices=[7,1,5,3,6,4],一次买卖最大利润 5(1→6)。”推导出 贪心 · 股票 I，并证明每次状态变化都不会漏掉答案？

中心结论：维护 minPrice;每天 max(profit, price-minPrice)。

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

在本站主例中，prices=[7,1,5,3,6,4],一次买卖最大利润 5(1→6)。

算法最终需要得到或观察：最大利润 5。

枚举全部决策组合会指数爆炸；贪心只保留能被交换论证或支配关系证明更优的选择。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“局部最优路标”，明确答案需要观察什么。
2. 2状态只维护 minPrice、当前 profit。
3. 3转移每一步按照 维护 minPrice;每天 max(profit, price-minPrice)。
4. 4收尾读取 最大利润 5。，并复核边界与复杂度。

局部选择必须带着“替换任何其他选择都不会更差”的证明。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：minPrice、当前 profit。

题目要求找出股票中能赚的钱最多的差价 这一题也有多个解法，可以用 DP，也可以用单调栈

维护 minPrice;每天 max(profit, price-minPrice)。

执行过程中持续维护：minPrice、当前 profit。

正确性依赖以下不变量：minPrice 是历史最低买入价。

面试时可以压缩为：一趟 min+profit,O(n)/O(1)。

落到当前题，执行机制可以压缩为：维护 minPrice;每天 max(profit, price-minPrice)。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入prices=[7,1,5,3,6,4],一次买卖最大利润 5(1→6)。 因为：维护 minPrice;每天 max(profit, price-minPrice)。
2. 2维护历史最低价 minPrice只能先买后卖一次。 因为：贪心:用历史最低买价最大化利润。
3. 3day 2: 若卖出利润 4,best=4; minPrice=1尝试以历史最低买入。 因为：O(n) 一遍。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5day 4: 若卖出利润 5,best=5; minPrice=1尝试以历史最低买入。 因为：O(n) 一遍。
6. 6day 5: 若卖出利润 3,best=5; minPrice=1尝试以历史最低买入。 因为：O(n) 一遍。
7. 7维护历史最低价 minPrice只能先买后卖一次。 因为：贪心:用历史最低买价最大化利润。
8. 8收尾与复杂度最大利润 5。 因为：时间 O(n) · 空间 O(1)。维护 minPrice;每天 max(profit, price-minPrice)。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 模拟 DP
func maxProfit(prices []int) int {
	if len(prices) < 1 {
		return 0
	}
	min, maxProfit := prices[0], 0
	for i := 1; i < len(prices); i++ {
		if prices[i]-min > maxProfit {
			maxProfit = prices[i] - min
		}
		if prices[i] < min {
			min = prices[i]
		}
	}
	return maxProfit
}

// 解法二 单调栈
func maxProfit1(prices []int) int {
	if len(prices) == 0 {
		return 0
	}
	stack, res := []int{prices[0]}, 0
	for i := 1; i < len(prices); i++ {
		if prices[i] > stack[len(stack)-1] {
			stack = append(stack, prices[i])
		} else {
			index := len(stack) - 1
			for ; index >= 0; index-- {
				if stack[index] < prices[i] {
					break
				}
			}
			stack = stack[:index+1]
			stack = append(stack, prices[i])
		}
		res = max(res, stack[len(stack)-1]-stack[0])
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
    // 1. 主例
    //    输入：mode="buy-sell-stock", prices=[7,1,5,3,6,4]
    //    期望：最大利润 5。
    //
    // 2. 失败 / 未命中
    //    检查：允许多次买卖不是本题。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC122 多次；LC123 两笔
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意prices=[7,1,5,3,6,4],一次买卖最大利润 5(1→6)。
2. 2重复枚举全部决策组合会指数爆炸；贪心只保留能被交换论证或支配关系证明更优的选择。
3. 3优化维护 minPrice;每天 max(profit, price-minPrice)。
4. 4证明minPrice 是历史最低买入价。
5. 5复杂度时间 O(n)，空间 O(1)