309 (高)334

309. Best Time to Buy and Sell Stock with Cooldown

<Array> 309 (高)334

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1) return 0;
        
        int n = prices.length;
        int[] hold = new int[n];
        int[] unhold = new int[n];
        
        hold[0] = -prices[0];
        for(int i = 1; i < n; i++){
            if(i == 1){
                hold[i] = Math.max(hold[i - 1], -prices[1]);
            }else{
                hold[i] = Math.max(hold[i - 1], unhold[i - 2] - prices[i]);
            }
            unhold[i] = Math.max(unhold[i - 1], hold[i - 1] + prices[i]);
        }
        return unhold[n - 1];
    }
}

334. Increasing Triplet Subsequence

如果m1大于等于当前数字,则将当前数字赋给m1;如果m1小于当前数字且m2大于等于当前数字,那么将当前数字赋给m2,一旦m2被更新了,说明一定会有一个数小于m2,那么我们就成功的组成了一个长度为2的递增子序列,所以我们一旦遍历到比m2还大的数,我们直接返回ture。如果我们遇到比m1小的数,还是要更新m1,有可能的话也要更新m2为更小的值,毕竟m2的值越小,能组成长度为3的递增序列的可能性越大

class Solution {
    public boolean increasingTriplet(int[] nums) {
       int m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE;
        for(int a : nums){
            if(m1 >= a) m1 = a;
            else if(m2 >= a) m2 = a;
            else return true;
        }
        return false;
    }
}
上一篇:力扣309——最佳买卖股票时机含冷冻期


下一篇:第十七组 Alpha 冲刺(1/3)