贪心

跳跃游戏

public boolean canJump(int[] nums) {
    if(nums.length ==1) return true;
    int coverRange = 0;
    for(int i=0; i<=coverRange; i++){ // 遍历coverRange，因为coverRange是当前可以跳跃的最大距离，所以遍历coverRange即可
        coverRange = Math.max(coverRange, i+nums[i]); // 站在第i个位置，最多可以跳nums[i]步
        if(coverRange >= nums.length-1) return true; // 如果coverRange >= nums.length-1（最后一个索引位置），则可以到达最后一个位置 
    }
    return false;
}

跳跃游戏II

public int jump(int[] nums) {
    if(nums.length == 1) return 0;
    int current = 0; // 当前跳跃的步数
    int next = 0; // 下一步跳跃的最大距离
    int result = 0; // 结果

    for(int i = 0; i<nums.length-1;i++){
        next=Math.max(i+nums[i],next); // 站在第i个位置，最多可以跳nums[i]步
        if(i == current){ // 到达当前跳的边界，必须跳一次
            result ++; 
            current = next; // 更新当前边界到下一跳边界
            if(current >= nums.length - 1) break; // 已经能跳到最后，提前退出
        }
    }
    return result;
}

加油站

• 如果总油量小于总消耗量，则无法完成环路

public int canCompleteCircuit(int[] gas, int[] cost) {
    int curSum = 0;       // 当前从起点到当前位置的净油量（局部判断）
    int totalSum = 0;     // 总体油量（全局判断）
    int index = 0;        // 可能的起始点

    for (int i = 0; i < gas.length; i++) {
        int gain = gas[i] - cost[i]; 
        curSum += gain;      // 当前路径净油
        totalSum += gain;    // 总体净油

        if (curSum < 0) { // 油不够了
            // 当前起点不行，说明从 index 到 i 之间都不能做起点
            index = i + 1;   // 更新起点为下一个
            curSum = 0;      // 重置局部净油
        }
    }
    // 如果总油量 < 总花费，无解，返回 -1。否则返回找到的起点。
    if (totalSum < 0) return -1;
    return index;
}

分发糖果

/**
     分两个阶段
     1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
     2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
*/
public int candy(int[] ratings) {
    int len = ratings.length;
    int[] candyVec = new int[len];
    candyVec[0] = 1;
    for (int i = 1; i < len; i++) {
        // 处理了「比左边高」的所有情况
        // 如果当前 ratings[i] > ratings[i - 1]，说明你比左边分高 → 糖果也得多：+1
        // 否则（等于或更小），给 1 就行
        candyVec[i] = (ratings[i] > ratings[i - 1]) ? candyVec[i - 1] + 1 : 1;
    }
    for (int i = len - 2; i >= 0; i--) { // len-2 是因为从倒数第二个开始处理 因为倒数第一个没有右边邻居
        // 处理了「比右边高」的所有情况
        // 注意：不能直接赋值为 candyVec[i + 1] + 1，因为可能左边也已经给了一个较大的值（从前面那一轮）
        // 所以取最大值：candyVec[i] = max(原有值, candyVec[i+1] + 1)
        if (ratings[i] > ratings[i + 1]) {
            candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
        }
    }
    int ans = 0;
    for (int num : candyVec) {
        ans += num;
    }
    return ans;
}

汇总区间

public List<String> summaryRanges(int[] nums) {
    List<String> res = new ArrayList<>();
    int start = 0; 
    int end = nums.length;
    while(start<end){
        int low = start; // low 是当前区间的起始位置
        start++;
        while(start<end && nums[start] == nums[start-1] + 1) start++; // 如果当前元素与前一个元素连续，则继续遍历
        int high = start-1; // high 是当前区间的结束位置
        StringBuilder sb = new StringBuilder(Integer.toString(nums[low])); // 将当前区间的起始位置转换为字符串
        if(low<high){
            sb.append("->"); // 如果当前区间有多个元素，则添加"->"
            sb.append(Integer.toString(nums[high])); // 将当前区间的结束位置转换为字符串
        }
        res.add(sb.toString()); // 将当前区间添加到结果列表中
    }
    return res;
}

合并区间

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) return new int[0][2]; // 如果intervals为空，则返回空数组
    // 1. 排序：按起始时间升序
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // 按起始位置升序排序
    List<int[]> merged = new ArrayList<>(); // 存储合并后的区间
    int[] current = intervals[0]; // 当前区间
    merged.add(current); // 将当前区间加入合并后的区间

    for (int i = 1; i < intervals.length; i++) { // 从第二个区间开始遍历
        int[] next = intervals[i]; // 下一个区间
        // 2. 检查是否重叠：如果当前的 end >= 下一个的 start，就合并
        if (current[1] >= next[0]) { // 如果当前区间的end >= 下一个区间的start，说明重复了，合并
            current[1] = Math.max(current[1], next[1]); // 合并 选择两个区间的end中较大的一个
        } else { // 如果不重叠，直接加入
            current = next; // 更新当前区间
            merged.add(current); // 将当前区间加入合并后的区间
        }
    }
    return merged.toArray(new int[merged.size()][]); // 将合并后的区间转换为数组
}

插入区间

区间分成三类：

• 完全在newInterval之前
• 和newInterval有重叠
• 完全在newInterval之后

public int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> result = new ArrayList<>();
    int i = 0;
    int n = intervals.length;
    // 1. 先添加所有结束早于 newInterval 开始的区间
    while (i < n && intervals[i][1] < newInterval[0]) { // 当现在的区间结束早于newInterval的开始，说明没有重叠，直接加入结果
        result.add(intervals[i]);
        i++;
    }
    // 2. 合并所有和 newInterval 重叠的区间
    while (i < n && intervals[i][0] <= newInterval[1]) { // 当现在的区间开始早于newInterval的结束，说明有重叠，合并
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]); // 开始位置取两个区间的开始位置中较小的
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]); // 结束位置取两个区间的结束位置中较大的
        i++;
    }
    // 只有在把所有重叠区间都处理完之后，才能确定最终合并区间的完整范围
    result.add(newInterval);
    // 3. 添加剩下所有区间
    while (i < n) { // 把和新区间完全不重叠、且在新区间之后的区间，直接加进结果
        result.add(intervals[i]);
        i++;
    }
    return result.toArray(new int[result.size()][]);
}

用最少的箭射爆气球

• 更新为最小右边界，是为了保证当前这支箭射出去的范围，能尽可能打到所有重叠气球。

public int findMinArrowShots(int[][] points) {
    Arrays.sort(points, (a,b)-> Integer.compare(a[0],b[0]));
    int count =1;
    for(int i = 1; i<points.length; i++){
        if(points[i][0] <= points[i-1][1]){ // 如果当前气球的开始位置小于等于上一个气球的结束位置，说明两个气球重叠 比如[1,2]和[2,3]
            points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 更新重叠气球最小右边界
        } else{
            count++; // 需要一支箭
        }
    }
    return count;
}