121 && 122. 买卖股票的最佳时机

第一题：

Problem: 121. 买卖股票的最佳时机

思路

题目要求只能在某一天买入股票，在另一天卖出，把股票的价格看成一个高度图，只要求出只能从前向后走的情况下最大下降量即可。

因此，在第一题中，我们从后向前遍历数组，保存到目前为止价格的最小值和结果的预估值。然后尝试在当前位置购入股票，并更新价格最小值。从前向后做的话方法类似。

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        int curMax = prices[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            ans = Math.max(ans, curMax - prices[i]);
            curMax = Math.max(prices[i], curMax);
        }
        return ans;
    }
}

踩坑

起初使用过动态规划的思想来做，多开了一个最小值数组。后面发现dp[i]只和dp[i + 1]有关，注意到这个数组是不必要的。

第二题

Problem: 122. 买卖股票的最佳时机 II

思路

本题和上一题的区别是可以选择多次购入卖出股票。和上一题一样，思考一个下山的过程，只要下山就可以获得奖励，上山也没有惩罚。

因此使用贪心的思想，对于某一天的股票，只要价格比上一天低就可以售出，用反证法就可以证明。

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n;i++) {
            if (prices[i] > prices[i - 1]) {
                ans += prices[i] - prices[i - 1];
            }
        }
        return ans;
    }
}