1.买卖股票的最佳时机No.121

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        // 初始化买入价格为最大值，最大利润为 0
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        // 遍历价格数组
        for (int price : prices) {
            // 更新最低买入价格
            if (price < minPrice) {
                minPrice = price;
            }
            // 计算当前价格卖出的利润
            else {
                maxProfit = Math.max(maxProfit, price - minPrice);
            }
        }

        return maxProfit;
    }
}

2.跳跃游戏No.55

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;  // 初始化为 0，表示起始位置能够到达的最远距离

        // 遍历数组
        for (int i = 0; i < nums.length; i++) {
            // 如果当前位置不可达，返回 false
            if (i > maxReach) {
                return false;
            }
            // 更新能够到达的最远位置
            maxReach = Math.max(maxReach, i + nums[i]);
            // 如果能够到达最后一个位置，返回 true
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }

        return false;  // 遍历结束，若不能到达最后一个位置，则返回 false
    }
}

public boolean canJump(int[] nums) {
        if(nums.length==1) return true;
        int cover = 0;
        for(int i = 0;i<=cover;i++){
            cover = Math.max(cover,i+nums[i]);
            if(cover>=nums.length-1){
                return true;
            }
        }
        return false;
    }

3.跳跃游戏IINo.45

class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        
        // 如果数组长度为 1，不需要跳跃
        if (n == 1) return 0;
        
        int jumps = 0;
        int farthest = 0;
        int currentEnd = 0;
        
        // 遍历到倒数第二个元素即可
        for (int i = 0; i < n ; i++) {
            // 更新能到达的最远位置
            farthest = Math.max(farthest, i + nums[i]);
            
            // 如果到达了当前区间的末尾，进行跳跃
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                
                // 如果当前区间的末尾已经能够到达最后一个位置，提前结束
                if (currentEnd >= n - 1) {
                    break;
                }
            }
        }
        
        return jumps;
    }
}

public int jump(int[] nums) {
        if(nums.length==1) return 0;
        int curr = 0;
        int next = 0;
        int jump = 0;
        for(int i = 0;i<nums.length;i++){
            next = Math.max(next,i+nums[i]);
            if(i==curr){
                jump++;
                curr = next;
                if(curr>=nums.length-1) break;
            }
        }
        return jump;
    }

4.划分字母区间No.763

• 思路
  • 统计每一个字符最后出现的位置
  • 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

class Solution {
    public List<Integer> partitionLabels(String s) {
        // Step 1: 记录每个字符最后出现的位置
        int[] lastIndex = new int[26];  // 因为字符是小写字母，共 26 个
        for (int i = 0; i < s.length(); i++) {
            lastIndex[s.charAt(i) - 'a'] = i;  // 更新字符的最后出现位置
        }

        List<Integer> result = new ArrayList<>();
        int currentEnd = 0;  // 当前片段的结束位置
        int start = 0;  // 当前片段的起始位置

        // Step 2: 遍历字符串，划分片段
        for (int i = 0; i < s.length(); i++) {
            currentEnd = Math.max(currentEnd, lastIndex[s.charAt(i) - 'a']);  // 更新当前片段的结束位置
            if (i == currentEnd) {  // 如果当前索引达到了当前片段的结束位置
                result.add(i - start + 1);  // 记录当前片段的长度
                start = i + 1;  // 更新下一个片段的起始位置
            }
        }

        return result;
    }
}