Leetcode — 顶级访谈 – 买卖股票的最佳时机

这是一个简单的问题，描述如下：

给你一个数组价格，其中prices[i]是给定股票第i天的价格。 您希望通过选择某一天买入一只股票并选择未来的另一天卖出该股票来最大化您的利润。 返回您可以从本次交易中获得的最大利润。如果无法获得任何利润，则返回0。 示例1： 输入：价格 = [7,1,5,3,6,4] 输出：5 说明：第 2 天买入（价格 = 1），第 5 天卖出（价格 = 6），利润 = 6-1 = 5。 请注意，不允许在第 2 天买入并在第 1 天卖出，因为您必须在卖出之前买入。 示例2： 输入：价格 = [7,6,4,3,1] 输出：0 说明：在这种情况下，没有进行任何交易，最大利润 = 0。 限制： 1

起初你会考虑排序并获得更小和更大的数字，但可能从数组中你可能会得到前后不同的范围或数字，这会导致差异与预期不符，所以忘记排序。

解决这种情况的一个好方法是在迭代数组时考虑最小值和最大值以及差异。如果最小值小于预期，则重置所有内容，否则继续前进并在小于最大值时更新最大值，并且始终获取差异，而不仅仅是最大值，否则当我们得到小于最小值但不是大最大值时，您可能会失败.

class Solution {
    public int maxProfit(int[] prices) {

        int min = prices[0];
        int max = prices[0];
        int diff = 0;

        for(int i=1;i<prices.length;i++) {
            if(min > prices[i]){
                min = prices[i];
                max = prices[i];
            } else if (max < prices[i]) {
                max = prices[i];
            }

            if(diff < (max - min)) {
                diff = max - min;
            }
        }

        return diff;
    }
}

运行时间：2 毫秒，比 77.66% 的 java 在线提交的最佳买卖股票时间要快。

内存使用量：61.4 mb，低于 java 在线提交的买卖股票最佳时机的 80.34%。

稿定PPT

海量PPT模版资源库

下载

您仍然可以进一步改进，删除 min 并仅使用 max，但差异并不大，但仍然是性能改进。

—

就是这样！如果还有什么要讨论的，请随时发表评论，如果我错过了任何内容，请告诉我，以便我进行相应更新。

直到下一篇文章！ :)