LeetCode贪心算法全解析：从基础到高级应用

public class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // 将孩子的胃口值和饼干的尺寸都排序
        Arrays.sort(g);
        Arrays.sort(s);
        int childIndex = 0; // 当前考虑的孩子的索引
        int cookieIndex = 0; // 当前考虑的饼干的索引
        // 遍历所有的饼干，尝试满足尽可能多的孩子
        while (childIndex < g.length && cookieIndex < s.length) {
            // 如果当前饼干可以满足当前孩子的胃口，给这个孩子，并考虑下一个孩子
            if (s[cookieIndex] >= g[childIndex]) {
                childIndex++;
            }
            // 无论是否满足当前孩子，都考虑下一块饼干
            cookieIndex++;
        }
        // 返回满足的孩子的数量
        return childIndex;
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        // 遍历价格数组，只要今天的价格比昨天高，就进行一次买卖交易
        for (int i = 1; i < prices.length; i++) {
            // 如果今天的价格比昨天高，就可以获利
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
}

public class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0; // 最远可到达的位置
        // 遍历数组中的每个位置
        for (int i = 0; i < nums.length; i++) {
            // 如果当前位置已经超过了最远可到达的位置，说明无法到达最后一个位置
            if (i > maxReach) {
                return false;
            }
            // 更新最远可到达的位置
            maxReach = Math.max(maxReach, i + nums[i]);
            // 如果最远可到达的位置已经大于等于数组的最后一个位置，说明可以到达最后一个位置
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        // 遍历完数组后，如果最远可到达的位置大于等于数组的最后一个位置，说明可以到达最后一个位置
        return maxReach >= nums.length - 1;
    }
}

public class Solution {
    public int jump(int[] nums) {
        int jumps = 0; // 跳跃次数
        int currentEnd = 0; // 当前可以到达的最远位置
        int currentMax = 0; // 下一次可以到达的最远位置
        // 遍历数组中的每个位置（除了最后一个位置，因为一旦到达最后一个位置，就不需要再跳跃了）
        for (int i = 0; i < nums.length - 1; i++) {
            // 更新下一次可以到达的最远位置
            currentMax = Math.max(currentMax, i + nums[i]);
            // 如果到达了当前可以到达的最远位置，跳跃次数加1，并更新当前可以到达的最远位置
            if (i == currentEnd) {
                jumps++;
                currentEnd = currentMax;
                // 如果当前可以到达的最远位置已经大于等于数组的最后一个位置，提前结束循环
                if (currentEnd >= nums.length - 1) {
                    break;
                }
            }
        }
        return jumps;
    }
}

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        // 第一次遍历，从左到右，确保每个孩子的糖果数不小于其左侧孩子的糖果数（如果评分更高）
        for (int i = 0; i < n; i++) {
            // 每个孩子至少分配到1个糖果
            candies[i] = 1;
            // 如果当前孩子的评分高于左侧孩子的评分，当前孩子的糖果数应比左侧孩子多1
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        // 第二次遍历，从右到左，确保每个孩子的糖果数不小于其右侧孩子的糖果数（如果评分更高）
        for (int i = n - 2; i >= 0; i--) {
            // 如果当前孩子的评分高于右侧孩子的评分，当前孩子的糖果数应比右侧孩子多1
            // 注意：这里需要取较大的值，以确保同时满足左侧和右侧的约束条件
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }
        // 计算需要准备的最小糖果数目
        int total = 0;
        for (int candy : candies) {
            total += candy;
        }
        return total;
    }
}

public class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        // 按照区间的结束时间排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int count = 1; // 选择的区间数，至少有一个区间
        int end = intervals[0][1]; // 当前选择的区间的结束时间
        // 遍历排序后的区间
        for (int i = 1; i < intervals.length; i++) {
            // 如果当前区间的开始时间大于等于当前选择的区间的结束时间，说明这两个区间不重叠
            if (intervals[i][0] >= end) {
                count++;
                end = intervals[i][1];
            }
        }
        // 需要移除的区间的最小数量等于总区间数减去选择的区间数
        return intervals.length - count;
    }
}

public class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        // 按照气球的结束坐标排序
        // 注意：这里使用Integer.compare来避免溢出
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        int count = 1; // 射出的箭的数量，至少需要一支箭
        int arrowPos = points[0][1]; // 当前射出的箭的位置
        // 遍历排序后的气球
        for (int i = 1; i < points.length; i++) {
            // 如果当前气球的开始坐标大于当前射出的箭的位置，说明需要射出一支新的箭
            if (points[i][0] > arrowPos) {
                count++;
                arrowPos = points[i][1];
            }
        }
        return count;
    }
}

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int totalSurplus = 0; // 总的剩余油量
        int currentSurplus = 0; // 当前的剩余油量
        int startStation = 0; // 起始加油站的编号
        // 遍历所有的加油站
        for (int i = 0; i < n; i++) {
            // 计算当前加油站的剩余油量
            int surplus = gas[i] - cost[i];
            // 更新总的剩余油量和当前的剩余油量
            totalSurplus += surplus;
            currentSurplus += surplus;
            // 如果当前的剩余油量小于0，说明从startStation到i的路径不可行
            if (currentSurplus < 0) {
                // 将起点设置为下一个位置
                startStation = i + 1;
                // 重置当前的剩余油量
                currentSurplus = 0;
            }
        }
        // 如果总的剩余油量大于等于0，说明存在一个起点，可以绕环路行驶一周
        return totalSurplus >= 0 ? startStation : -1;
    }
}

public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        if (people == null || people.length == 0) {
            return new int[0][0];
        }
        // 按照身高降序排序，如果身高相同，则按照前面的人数升序排序
        Arrays.sort(people, (a, b) -> {
            if (a[0] != b[0]) {
                return b[0] - a[0]; // 身高降序
            } else {
                return a[1] - b[1]; // 前面的人数升序
            }
        });
        // 构建队列
        List<int[]> queue = new ArrayList<>();
        for (int[] person : people) {
            // 将每个人插入到队列的第k个位置
            queue.add(person[1], person);
        }
        // 将队列转换为数组并返回
        return queue.toArray(new int[queue.size()][]);
    }
}

public class Solution {
    public int monotoneIncreasingDigits(int N) {
        // 将数字转换为字符数组，方便操作
        char[] digits = String.valueOf(N).toCharArray();
        int n = digits.length;
        int flag = n; // 标记从哪一位开始需要设置为9
        // 从右向左遍历数字的每一位
        for (int i = n - 1; i > 0; i--) {
            // 如果当前位的数字大于下一位的数字，需要调整
            if (digits[i - 1] > digits[i]) {
                digits[i - 1]--; // 当前位的数字减1
                flag = i; // 更新标记，从当前位的下一位开始需要设置为9
            }
        }
        // 将标记位置及之后的所有位的数字都设置为9
        for (int i = flag; i < n; i++) {
            digits[i] = '9';
        }
        // 将字符数组转换为整数并返回
        return Integer.parseInt(new String(digits));
    }
}

public class Solution {
    public String removeKdigits(String num, int k) {
        // 特殊情况处理
        if (num.length() == k) {
            return "0";
        }
        // 使用栈来维护当前的数字序列
        Stack<Character> stack = new Stack<>();
        // 遍历数字的每一位
        for (char digit : num.toCharArray()) {
            // 如果当前位的数字小于栈顶的数字，且还可以移除数字，就弹出栈顶的数字
            while (!stack.isEmpty() && stack.peek() > digit && k > 0) {
                stack.pop();
                k--;
            }
            // 将当前位的数字压入栈中
            stack.push(digit);
        }
        // 如果k仍然大于0，继续弹出栈顶的数字
        while (k > 0) {
            stack.pop();
            k--;
        }
        // 将栈中的数字转换为字符串
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        // 反转字符串，因为栈是后进先出的
        result.reverse();
        // 移除前导零
        while (result.length() > 1 && result.charAt(0) == '0') {
            result.deleteCharAt(0);
        }
        return result.toString();
    }
}

// 更高效的实现，使用StringBuilder代替Stack
public class Solution {
    public String removeKdigits(String num, int k) {
        // 特殊情况处理
        if (num.length() == k) {
            return "0";
        }
        // 使用StringBuilder来模拟栈，维护当前的数字序列
        StringBuilder stack = new StringBuilder();
        // 遍历数字的每一位
        for (char digit : num.toCharArray()) {
            // 如果当前位的数字小于栈顶的数字，且还可以移除数字，就删除栈顶的数字
            while (stack.length() > 0 && stack.charAt(stack.length() - 1) > digit && k > 0) {
                stack.deleteCharAt(stack.length() - 1);
                k--;
            }
            // 将当前位的数字添加到栈中
            stack.append(digit);
        }
        // 如果k仍然大于0，继续删除栈顶的数字
        while (k > 0) {
            stack.deleteCharAt(stack.length() - 1);
            k--;
        }
        // 移除前导零
        int start = 0;
        while (start < stack.length() && stack.charAt(start) == '0') {
            start++;
        }
        // 如果所有数字都是零，返回"0"
        if (start == stack.length()) {
            return "0";
        }
        return stack.substring(start);
    }
}

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        int[] result = new int[0];
        // 枚举从第一个数组中选取的数字的个数i
        for (int i = Math.max(0, k - n); i <= Math.min(m, k); i++) {
            int j = k - i; // 从第二个数组中选取的数字的个数
            // 从第一个数组中选取i个数字，保持相对顺序，使得拼接后的数字最大
            int[] subsequence1 = maxSubsequence(nums1, i);
            // 从第二个数组中选取j个数字，保持相对顺序，使得拼接后的数字最大
            int[] subsequence2 = maxSubsequence(nums2, j);
            // 合并这两个子数组成一个最大的数组
            int[] merged = merge(subsequence1, subsequence2);
            // 更新结果，选择合并后的最大的数组
            if (compare(merged, 0, result, 0) > 0) {
                result = merged;
            }
        }
        return result;
    }

    // 从数组nums中选取k个数字，保持相对顺序，使得拼接后的数字最大
    private int[] maxSubsequence(int[] nums, int k) {
        if (k == 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] stack = new int[k];
        int top = -1;
        int remain = n - k; // 可以删除的数字的个数
        for (int i = 0; i < n; i++) {
            // 如果当前数字大于栈顶的数字，且还可以删除数字，就弹出栈顶的数字
            while (top >= 0 && stack[top] < nums[i] && remain > 0) {
                top--;
                remain--;
            }
            // 如果栈还没有满，将当前数字压入栈中
            if (top < k - 1) {
                stack[++top] = nums[i];
            } else {
                remain--;
            }
        }
        return stack;
    }

    // 合并两个子数组成一个最大的数组，保持各自的相对顺序
    private int[] merge(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] result = new int[m + n];
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) {
            // 比较两个子数组的剩余部分，选择较大的那个的当前数字
            if (compare(nums1, i, nums2, j) > 0) {
                result[k++] = nums1[i++];
            } else {
                result[k++] = nums2[j++];
            }
        }
        // 处理剩余的数字
        while (i < m) {
            result[k++] = nums1[i++];
        }
        while (j < n) {
            result[k++] = nums2[j++];
        }
        return result;
    }

    // 比较两个子数组的剩余部分，从索引i和j开始
    private int compare(int[] nums1, int i, int[] nums2, int j) {
        int m = nums1.length;
        int n = nums2.length;
        while (i < m && j < n) {
            if (nums1[i] != nums2[j]) {
                return nums1[i] - nums2[j];
            }
            i++;
            j++;
        }
        // 如果一个子数组是另一个子数组的前缀，较长的子数组更大
        return (m - i) - (n - j);
    }
}