力扣-股票问题

121. 买卖股票的最佳时机

原题链接:121.买卖股票的最佳时机
题解:只需要找到当天之前的最低价格,不停的用后面的价格减去前面的最低价格,取最大值即可。

     public int maxProfit(int[] prices) {
        int res = 0; // 结果
         for (int i = 0, min = Integer.MAX_VALUE; i < prices.length; i ++) {
             res = Math.max(res, prices[i] - min); // 不断用当天价格减去前面最低价格
             min = Math.min(min, prices[i]); // 更新最低价格
         }
         return res;
     }

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

原题链接:122. 买卖股票的最佳时机 II
题解:这道题和上一题的区别在于,上一题只能一次交易,这一题可以支持多次交易。 可以理解为,只要能收益,就进行交易。

    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 0; i + 1 < prices.length; i ++) {
            int profit = prices[i + 1] - prices[i]; // 后一天减去前一天 判断是否能够盈利
            if (profit > 0) res += profit; // 能够盈利则加入
        }
        return res;
    }

123. 买卖股票的最佳时机 III

原题链接:123. 买卖股票的最佳时机 III
题解:本题和上一题的区别在于,此题只能进行两次交易。 采用前后缀分解 求出最大前缀, 再求出最大后缀,二者之和即是最大收益。
从前往后遍历数组,分别求出每个区间内的最大收益。
从后往前遍历数组,分别求出每个区间内的最大收益。并在这个过程中记录下最大收益即可。

     public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] profit = new int[n + 1];  // 前面每一段时间每天的最大收益
        for (int i = 1, minp = Integer.MAX_VALUE; i <= n; i ++) {
            profit[i] = Math.max(profit[i - 1], prices[i - 1] - minp);
            minp = Math.min(minp, prices[i - 1]);
        }

        int res = 0;
        for (int i = n, maxp = 0; i > 0; i --) {
            int curMaxProfit = maxp - prices[i - 1]; // 后面每一段时间每天的最大收益
            res = Math.max(res, curMaxProfit + profit[i - 1]); // 前后缀 最大值相加与当前最大收益进行比较
            maxp = Math.max(maxp, prices[i - 1]);
        }

        return res;
    }

评论

暂无评论