股票买卖最佳时机：LeetCode121题解

题目LeetCode121

给定一个数组prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回0。

示例

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票

Python解法

代码示例（一次遍历）

class Solution: def maxProfit(self, prices: List[int]) -> int: min_pri = float('inf') max_pro = 0 for price in prices: max_pro = max(price - min_pri, max_pro) min_pri = min(price, min_pri) return max_pro

过程演示

Java解法

代码示例（一次遍历）

class Solution{ public int maxProfit(int[] prices){ int min_pri = Integer.MAX_VALUE; int max_pro = 0; for(int price : prices){ max_pro = Math.max(price - min_pri, max_pro); min_pri = Math.min(min_pri, price); } return max_pro; } }

C++ 解法

代码示例（一次遍历）

class Solution{ public: int maxProfit(vector<int>& prices){ int minPrice = INT_MAX; int maxProfit = 0; for (int price : prices) { maxProfit = max(maxProfit, price - minPrice); minPrice = min(minPrice, price); } return maxProfit; } };

三种语言设置最小值比较

Python

在 Python 中，要表示 “无穷大” 的初始最小值，直接用float("inf")就可以。它是 Python 内置的浮点型无穷大常量，能保证数组里任何价格都比它小，这样第一个价格就能顺利更新为当前的最小值。这种写法很直观，也不需要额外引入头文件或类。

Java

在 Java 里，没有直接的 “无穷大” 关键字，所以用Integer.MAX_VALUE来代替。它是java.lang.Integer类里的一个常量，代表int类型能表示的最大值，数值上等于2147483647。把初始最低价设为它，就能保证任何合法的股价（正整数）都比它小，后续遍历到的第一个价格会自动更新为新的最小值。

C++

C++ 中用INT_MAX表示int类型的最大值，它定义在<climits>头文件里（部分编译器也会通过其他头文件间接包含）。和 Java 类似，它是一个预定义的宏常量，代表int类型的最大取值，把它作为初始最小值，就能确保第一个价格一定能被更新为当前的最低价。