一. 力扣 121. 买卖股票的最佳时机

1. 题目解析

这道题很好理解, 相当于找最大值和最小值的问题

2. 算法原理

3. 代码

class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0];
        int ret = 0;
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            ret = Math.max(ret, prices[i] - min);
        }
        return ret;
    }
}

---

二. 力扣 122. 买卖股票的最佳时机 II

1. 题目解析

这道题相比于股票问题1, 少了个限制是, 可以多次买卖股票

2. 算法原理

这里提供两种思路, 一种是双指针, 一种是拆分交易, 时间复杂度都是O(N)

(1) 贪心+双指针

(2) 拆分交易

3. 代码

1. 算法1

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

2. 算法2

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