買賣股票的最佳時期(121)

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < prices.length; i++){
            min = Math.min(min, prices[i]);
            res = Math.max(res,prices[i] - min);
        }
        return res;
    }
}

• 感悟

貪心就是貪局部最優解, 擴散到全局

跳躍游戲(055)

class Solution {
    public boolean canJump(int[] nums) {
        int max_length = 0;
        int i = 0;
        for (; max_length >= i && i < nums.length; i++){
            max_length = Math.max(max_length, i + nums[i]);
        }
        return i == nums.length;
    }
}

• 分析

max_length來維護理論可達距離

跳躍游戲II(045)

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int res = 0;
        int curr = 0;
        int nextCurr = 0;
        for (int i = 0; i < n-1 ; i++){
            nextCurr = Math.max(nextCurr, i+ nums[i]);
            if (i == curr){
                curr = nextCurr;
                res++;
            }
        }
        return res;
    }
}

• 分析

curr 維護本次跳躍最大可達距離

nextCurr 通過遍歷途經點, 維護下次跳躍最大可達距離

劃分字母區間(763)

class Solution {
    public List<Integer> partitionLabels(String s) {
        int n = s.length();
        char[] charArray = s.toCharArray();
        int[] last = new int[26];
        for (int i = 0 ; i < n; i++){
            last[charArray[i]- 'a'] = i;
        }

        List<Integer> res = new ArrayList<>();
        int start = 0;
        int end = 0;
        for (int i = 0; i < n; i++){
            end = Math.max(end, last[charArray[i] - 'a']);
            if (end == i){
                res.add(end - start + 1);
                start = i+1;
            }
        }
        return res;
    }
}

• 分析

將字符串預處理, 產生每個字符的最大索引

提取[start,end]范圍內字符的最遠索引來更新end

• 感悟

遇到這種熟悉又陌生的題型真別怕, 先把陌生數據轉換成熟悉的, 這題就跟跳躍游戲II(045)一樣了