2022-02-22 「121. 买卖股票的最佳时机」

今日简单题：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

看题要求最大差值，知道是动态规划，但是规划方程只能推导出：

用暴力法可以通过自测用例，但数据量变大的时候，会提示超过时间限制，需要优化时间复杂度。

但是答案中的解释存在问题，说必须找到最低点后再购买的假设是错误的，因为最低点可能是最后一个值，或者差值较小，比如[10,12,7,8,3]，这种情况下最大差值是2；

优化后的思路应该是遍历一遍，把最小值和后面数的差值存起来，遇到大的取大的。

最后贴2种解法：

1.暴力法代码如下：

class Solution {

    public int maxProfit(int[] prices) {

        int ans = 0;

        for (int i = 0; i< prices.length-1; i++) {

            for (int j = i+1;j<prices.length;j++) {

                if (prices[j]>prices[i]) {

                    ans = Math.max(ans,prices[j]-prices[i]);

                }

            }

        }

        return ans;

    }

}

2.优化时间复杂度后：

class Solution {

    public int maxProfit(int[] prices) {

        int min = Integer.MAX_VALUE;

        int max = 0;

        for (int i = 0; i< prices.length; i++) {

            if (min > prices[i]) {

                min = prices[i];

            }

            else if (max < prices[i]-min) {

                max = prices[i]-min;

            }

        }

        return max;

    }

}