小白学算法：买卖股票的最佳时机！ (2)

如果当前节点不是最低价，那我们就将它卖出，然后计算卖出的收益（当前节点减去相对最低价），如果卖出的收益大于目前的最高收益，则将此值设置为最高收益。

这样循环完成之后最高收益就出来了，实现代码如下：

class Solution { public int maxProfit(int prices[]) { if (prices == null || prices.length == 0) return 0; int mp = 0; // 最高收益 int min = prices[0]; // 最低价 for (int i = 1; i < prices.length; i++) { if (prices[i] < min) { // 设定相对最低价 min = prices[i]; } else if (mp < (prices[i] - min)) { // 设定最高盈利 mp = prices[i] - min; } } return mp; } }

以上代码在 leetcode 中的结果如下图所示：

复杂度分析

时间复杂度：O(n)，只需要遍历一次。

空间复杂度：O(1)，只使用了常数个变量。

从以上的执行的结果可以看出，这段代码还算是比较理想的，这样面试官也会对你竖起大拇指了。

总结

本文我们计算了单次（一次买入和卖出）股票的最高收益，刚开始我们使用的是最简单粗暴的暴力枚举法，使用两层循环依次相减来求出最高收益值，但这种方法的执行效率太低。

然后我们经过观察折线图发现，只需要一次循环也能找出最高的收益值。我们只需要在每个节点做两个判断，第一：判断此节点是否为相对最小值，如果是，则记录下来；如果不是，则计算此值和相对最小值是否为当前最高收益，如果是，则记录下来。那么循环一圈之后，我们就能得出最高的收益了，并且执行的效率也很高。

你学会了吗？有不懂的地方或者更好的方法，欢迎评论区留言~