买卖股票的最佳时机

Best Time to Buy and Sell Stock

问题：买卖股票的最佳时机

考察：数组、动态规划

来源：DSA Prep / Citadel

链接：https://www.dsaprep.dev/blog/best-time-to-buy-and-sell-stock-leetcode-solution

Problem: Best Time to Buy and Sell Stock

Patterns: Array, Dynamic Programming

Recency: 3mo

Link: https://www.dsaprep.dev/blog/best-time-to-buy-and-sell-stock-leetcode-solution

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：从左到右维护到当前为止的最低买入价，用当前价格减最低价更新最大利润。卖出必须发生在买入之后，因此只需要一个历史最小值。

复杂度：时间 O(n)，空间 O(1)。