Leetcode-Array-122.买卖股票的最佳时机2

发表于 更新于 分类于 ， 阅读次数： 本文字数： 316 阅读时长 ≈ 1 分钟

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/?envType=study-plan-v2&envId=top-interview-150

思路

这道题目被大家喷的相当惨烈，出题者本身的目的可能是希望采用贪心或者动态规划，但是没设计好，导致题目实际上只需要累加所有的上升段即可。

代码

累加所有的涨幅，躲开所有的跌幅即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices) {
        int len=prices.length;
        int profit=0;
        int max=prices[0];
        int min=prices[0];
        for(int i=1;i<len;i++){
            if(prices[i]<max){ // 开始跌了
                profit+=(max-min);
                min=prices[i];
                max=prices[i];
            }else{ // 还在涨，继续持仓
                max=prices[i];
            }
        }
        return profit+(max-min);  // 有可能一直上涨
    }
}

上述代码是一直持仓到跌之前卖出，我们还可以每天进行卖出（实际上将一个长时间段的涨幅分割为每一天每一天的）。代码上会更加简单。

简而言之，如果 prices[i]>prices[i-1] ，就将其累加到 profit 中。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int profit=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]>prices[i-1]){
                profit+=prices[i]-prices[i-1];
            }
        }
        return profit;
    }
}

看起来第一种进行的算术运算少一些，但是第二种实际上会更快，因为没有那么多的分支结构。