算法 5（贪心算法、十大排序、技巧）

/* 零钱兑换：贪心 */
int coinChangeGreedy(int[] coins, int amt) {
    // 假设 coins 列表有序
    int i = coins.length - 1;
    int count = 0;
    // 循环进行贪心选择，直到无剩余金额
    while (amt > 0) {
        // 找到小于且最接近剩余金额的硬币
        while (i > 0 && coins[i] > amt) i--;
        // 选择 coins[i]
        amt -= coins[i];
        count++;
    }
    // 若未找到可行方案，则返回 -1
    return amt == 0 ? count : -1;
}

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int count = 0;
    int start = s.length - 1;
    // 遍历胃口，先喂饱大胃口
    for (int index = g.length - 1; index >= 0; index--) {
        if(start >= 0 && g[index] <= s[start]) {
            start--;
            count++;
        }
    }
    return count;
}

public boolean lemonadeChange(int[] bills) {
    int five = 0;
    int ten = 0;
    for (int i = 0; i < bills.length; i++) {
        if (bills[i] == 5) five++;
        else if (bills[i] == 10) {
            five--;
            ten++;
        } else if (bills[i] == 20) {
            if (ten > 0) {
                ten--;
                five--;
            } else {
                five -= 3;
            }
        }
        if (five < 0 || ten < 0) return false;
    }
    return true;
}

// 从前向后
for (int i = 1; i < ratings.size(); i++) {
    if (ratings[i] > ratings[i - 1]) candy[i] = candy[i - 1] + 1;
}

// 从后向前
for (int i = ratings.size() - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1] ) {
        candy[i] = max(candy[i], candy[i + 1] + 1);
    }
}

public int candy(int[] ratings) {
    int len = ratings.length;
    int[] candy = new int[len];
    candy[0] = 1;
    for (int i = 1; i < len; i++) {
        candy[i] = (ratings[i] > ratings[i - 1]) ? candy[i - 1] + 1 : 1;
    }
    for (int i = len - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candy[i] = Math.max(candy[i], candy[i + 1] + 1);
        }
    }
    int res = 0;
    for (int num : candy) res += num;
    return res;
}

public int[][] reconstructQueue(int[][] people) {
    // 身高从大到小排（身高相同k小的站前面）
    Arrays.sort(people, (a, b) -> {
        if (a[0] == b[0]) return a[1] - b[1]; // a - b 是升序排列，故在a[0] == b[0]的狀況下，會根據k值升序排列
        return b[0] - a[0]; // b - a 是降序排列，在a[0] != b[0]，的狀況會根據h值降序排列
    });
    LinkedList<int[]> que = new LinkedList<>();
    for (int[] p : people) {
        que.add(p[1],p); // Linkedlist.add(index, value)，會將value插入到指定index裡
    }
    return que.toArray(new int[0][]);
}

public boolean canJump(int[] nums) {
    if (nums.length == 1) return true;
    // 覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
    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;
}

int jump(int[] nums) {
    if (nums.length == 1) return 0;
    int curDistance = 0; // 当前覆盖最远距离下标
    int count = 0; // 记录走的最大步数
    int nextDistance = 0; // 下一步覆盖最远距离下标
    for (int i = 0; i < nums.length; i++) {
        nextDistance = Math.max(nums[i] + i, nextDistance); // 更新下一步覆盖最远距离下标
        if (i == curDistance) { // 遇到当前覆盖最远距离下标
            count++; // 需要走下一步
            curDistance = nextDistance; // 更新当前覆盖最远距离下标
            if (nextDistance >= nums.length - 1) break; // 当前覆盖最远距到达集合终点，不用做count++操作了，直接结束
        }
    }
    return count;
}

public List<Integer> partitionLabels(String S) {
    List<Integer> list = new LinkedList<>(); // 用于存储每个片段的长度
    // 1. 预处理：记录每个字符在字符串中出现的【最后一次】下标位置
    int[] edge = new int[26]; // 对应26个小写字母
    char[] chars = S.toCharArray();
    // 遍历字符串，更新每个字符的最后出现位置
    for (int i = 0; i < chars.length; i++) {
        edge[chars[i] - 'a'] = i;
    }
    // 2. 贪心策略：遍历字符串，确定分割点
    int idx = 0; // 当前片段中所有字符能到达的【最远边界】
    int last = 0; // 当前片段的开始位置，用于计算长度
    for (int i = 0; i < chars.length; i++) {
        // 获取当前字符的最远边界，并更新当前片段的整体最远边界
        idx = Math.max(idx, edge[chars[i] - 'a']);
        // 如果当前位置 i 达到了当前片段的最远边界 idx
        // 说明从 "last + 1" 到 "i" 这一段包含的所有字符，都不会在 i 之后出现
        // 这就是一个合法的分割点
        if (i == idx) {
            // 计算长度：当前位置 - 开始位置 + 1
            list.add(i - last + 1);
            // 更新上一次结束位置
            last = i + 1;
        }
    }
    return list;
}

public int[][] merge(int[][] intervals) {
    List<int[]> result = new ArrayList<>();
    // 如果区间集合为空，直接返回空数组
    if (intervals == null || intervals.length == 0) return result.toArray(new int[0][]);
    // 1. 排序：按照区间的起始位置（左边界）进行升序排序
    Arrays.sort(intervals, (a,b)->a[0]-b[0]);
    // 2. 将第一个区间加入结果集
    result.add(intervals[0]);
    // 3. 遍历剩余区间
    for (int i = 1; i < intervals.length; i++) {
        // 获取结果集中最后一个区间（当前正在合并的区间）
        int[] lastInterval = result.get(result.size() - 1);
        // 情况一：如果 "最后一个区间的右边界" >= "当前遍历区间的左边界"，则说明重叠
        if (lastInterval[1] >= intervals[i][0]) lastInterval[1] = Math.max(lastInterval[1], intervals[i][1]); // 合并区间：更新右边界，取两者的最大值，因为左边界已经是最小的（已排序）
        // 情况二：区间不重叠，直接将当前区间加入结果集
        else result.add(intervals[i]);
    }
    // 将 List<int[]> 转换为二维数组返回
    return result.toArray(new int[0][]);
}

public int findMinArrowShots(int[][] points) {
    // 1. 排序：根据气球直径的【起始坐标】从小到大排序
    Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
    // 2. 初始化箭的数量，只要数组不为空，至少需要一支箭
    int count = 1;
    // 3. 遍历气球数组，从第二个气球开始
    for (int i = 1; i < points.length; i++) {
        // 情况一：当前气球的左边界 > 前一个气球的右边界，说明两个气球完全没有重叠（甚至不挨着），一支箭无法同时射爆它们，需要增加一支箭
        // 注意：这里必须是 >，如果是 = 说明刚好挨着，一支箭在交界处也能射爆
        if (points[i][0] > points[i - 1][1]) count++;
        // 情况二：当前气球的左边界 <= 前一个气球的右边界，说明两个气球有重叠部分，可以用同一支箭射爆
        else points[i][1] = Math.min(points[i][1], points[i - 1][1]); // 贪心策略：更新重叠区域的最小右边界
    }
    return count;
}

public int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;
    int i = 0; // i 代表我们尝试作为起点的那个加油站的下标

    // 外层循环：尝试每一个可能的起点
    // 注意：这里的 i 不是简单的 i++，而是跳跃式的
    while (i < n) {
        int sumOfGas = 0; // 记录当前尝试的路径中，累计获得的汽油量
        int sumOfCost = 0; // 记录当前尝试的路径中，累计消耗的汽油量
        int cnt = 0;     // 记录当前从起点 i 出发，成功走过的加油站数量

        // 内层循环：模拟从起点 i 出发，尝试走完一圈 (n 个站)
        while (cnt < n) {
            // 计算当前到达的加油站的实际下标
            // 使用取模运算 % n 来处理环形数组（即走完最后一个回到第一个）
            int j = (i + cnt) % n;

            sumOfGas += gas[j];   // 加上当前站的油
            sumOfCost += cost[j]; // 减去去下一站的路费

            // 核心判断：如果累计消耗 > 累计油量，说明油不够了，车跑不动了
            if (sumOfCost > sumOfGas) {
                break; // 当前起点 i 失败，跳出内层循环
            }
            cnt++; // 如果油够，继续尝试下一个站
        }

        // 如果 cnt == n，说明内层循环完整跑完了一圈都没有 break
        if (cnt == n) {
            return i; // 找到了合法的起点，直接返回
        } else {
            // 如果没跑完一圈就失败了，我们需要更换起点
            // 关键优化：i = i + cnt + 1
            // 解释：从 i 到 i+cnt 这些站点都不可能作为起点（见下方原理解析）
            // 所以下一个尝试的起点直接跳到失败点的下一个位置
            i = i + cnt + 1;
        }
    }
    // 如果所有可能的起点都试过了（或者跳过了），都没成功，返回 -1
    return -1;
}

/* 选择排序 */
void selectionSort(int[] nums) {
    int n = nums.length;
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i; // 用k来记录未排序区间内的最小元素
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k]) k = j;
        }
        // 将该最小元素与未排序区间的首个元素交换
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

/* 冒泡排序 */
void bubbleSort(int[] nums) {
    // 外循环：未排序区间为 [0, i]
    for (int i = nums.length - 1; i > 0; i--) {
        boolean flag = false;
        // 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交换 nums[j] 与 nums[j + 1]
                int tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                boolean = true;
            }
        }
        if(!flag) break;
    }
}

/* 插入排序 */
void insertionSort(int[] nums) {
    // 外循环：未排序区间为 [i, n-1]
    // i 指向当前待插入的元素（摸到的这张“牌”）
    for (int i = 1; i < nums.length; i++) {
        // 暂存当前待插入的元素，防止在后续移动过程中被覆盖
        int base = nums[i];
        // j 指向“已排序”区间的最后一个元素
        int j = i - 1;

        // 内循环：在已排序区间 [0, i-1] 中寻找插入位置
        // 只要 j 还在数组范围内，且已排序区的元素比 base 大，说明 base 应该插在这个元素的前面，所以把这个大元素向后挪一位
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // 元素后移（腾位置）
            j--;                   // 指针前移（继续向前寻找更小的元素）
        }

        // 循环结束时，j 指向的是第一个“小于或等于” base 的元素，所以 j + 1 就是 base 应该插入的正确空位
        nums[j + 1] = base;
    }
}

/* 元素交换 */
void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* 哨兵划分 */
int partition(int[] nums, int left, int right) {
    // 以 nums[left] 为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;          // 从右向左找首个小于基准数的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 从左向右找首个大于基准数的元素
        swap(nums, i, j); // 交换这两个元素
    }
    swap(nums, i, left);  // 将基准数交换至两子数组的分界线
    return i;             // 返回基准数的索引
}

/* 快速排序 */
void quickSort(int[] nums, int left, int right) {
    // 子数组长度为 1 时终止递归
    if (left >= right) return;
    // 哨兵划分
    int pivot = partition(nums, left, right);
    // 递归左子数组、右子数组
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

/* 选取三个候选元素的中位数 */
int medianThree(int[] nums, int left, int mid, int right) {
    int l = nums[left], m = nums[mid], r = nums[right];
    if ((l <= m && m <= r) || (r <= m && m <= l))
        return mid; // m 在 l 和 r 之间
    if ((m <= l && l <= r) || (r <= l && l <= m))
        return left; // l 在 m 和 r 之间
    return right;
}

/* 哨兵划分（三数取中值） */
int partition(int[] nums, int left, int right) {
    // 选取三个候选元素的中位数
    int med = medianThree(nums, left, (left + right) / 2, right);
    // 将中位数交换至数组最左端
    swap(nums, left, med);
    // 以 nums[left] 为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left])
            j--;          // 从右向左找首个小于基准数的元素
        while (i < j && nums[i] <= nums[left])
            i++;          // 从左向右找首个大于基准数的元素
        swap(nums, i, j); // 交换这两个元素
    }
    swap(nums, i, left);  // 将基准数交换至两子数组的分界线
    return i;             // 返回基准数的索引
}

/* 快速排序（递归深度优化） */
void quickSort(int[] nums, int left, int right) {
    // 子数组长度为 1 时终止
    while (left < right) {
        // 哨兵划分操作
        int pivot = partition(nums, left, right);
        // 对两个子数组中较短的那个执行快速排序
        if (pivot - left < right - pivot) {
            quickSort(nums, left, pivot - 1); // 递归排序左子数组
            left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
        } else {
            quickSort(nums, pivot + 1, right); // 递归排序右子数组
            right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
        }
    }
}

/* 合并左子数组和右子数组 */
void merge(int[] nums, int left, int mid, int right) {
    // 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
    // 创建一个临时数组 tmp，对应区间为 [0, right - left]，用于存放合并后的结果
    int[] tmp = new int[right - left + 1];
    // 初始化左子数组和右子数组的起始索引
    int i = left, j = mid + 1, k = 0;
    // 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
            tmp[k++] = nums[i++];
        else
            tmp[k++] = nums[j++];
    }
    // 将左子数组和右子数组的剩余元素复制到临时数组中
    while (i <= mid) tmp[k++] = nums[i++];
    while (j <= right) tmp[k++] = nums[j++];
    // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
    for (k = 0; k < tmp.length; k++) nums[left + k] = tmp[k];
}

/* 归并排序 */
void mergeSort(int[] nums, int left, int right) {
    // 终止条件
    if (left >= right) return; // 当子数组长度为 1 时终止递归
    // 划分阶段
    int mid = left + (right - left) / 2; // 计算中点
    mergeSort(nums, left, mid); // 递归左子数组
    mergeSort(nums, mid + 1, right); // 递归右子数组
    // 合并阶段
    merge(nums, left, mid, right);
}

class Solution {
    public ListNode sortList(ListNode head) {
        // 如果链表为空或者只有一个节点，无需排序
        if (head == null || head.next == null) return head;
        // 找到中间节点 head2，并断开 head2 与其前一个节点的连接
        // 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
        ListNode head2 = middleNode(head);
        // 分治
        head = sortList(head);
        head2 = sortList(head2);
        // 合并
        return mergeTwoLists(head, head2);
    }

    // 876. 链表的中间结点（快慢双指针迭代法）
    private ListNode middleNode(ListNode head) {
        ListNode pre = head;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            pre = slow; // 记录 slow 的前一个节点
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null; // 断开 slow 的前一个节点和 slow 的连接
        return slow;
    }

    // 21. 合并两个有序链表（独立双指针迭代法）
    private ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(); // 用哨兵节点简化代码逻辑
        ListNode cur = dummy; // cur 指向新链表的末尾
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1; // 把 list1 加到新链表中
                list1 = list1.next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur.next = list2; // 把 list2 加到新链表中
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1 != null ? list1 : list2; // 拼接剩余链表
        return dummy.next;
    }
}

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(int[] nums, int n, int i) {
    while (true) {
        // 判断节点 i, l, r 中值最大的节点，记为 ma
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int ma = i;
        if (l < n && nums[l] > nums[ma]) ma = l;
        if (r < n && nums[r] > nums[ma]) ma = r;
        // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if (ma == i) break;
        // 交换两节点
        int temp = nums[i];
        nums[i] = nums[ma];
        nums[ma] = temp;
        // 循环向下堆化
        i = ma;
    }
}

/* 堆排序 */
void heapSort(int[] nums) {
    // 建堆操作：堆化除叶节点以外的其他所有节点
    for (int i = nums.length / 2 - 1; i >= 0; i--) siftDown(nums, nums.length, i);
    // 从堆中提取最大元素，循环 n-1 轮
    for (int i = nums.length - 1; i > 0; i--) {
        // 交换根节点与最右叶节点（交换首元素与尾元素）
        int tmp = nums[0];
        nums[0] = nums[i];
        nums[i] = tmp;
        // 以根节点为起点，从顶至底进行堆化
        siftDown(nums, i, 0);
    }
}

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        int t = temperatures[i];
        // 【及时循环去掉无用数据，并更新结果】第i天新温度大于栈顶第j天温度，循环弹出栈顶第j天，并且填入第j天的结果
        while (!stack.isEmpty() && t > temperatures[stack.peek()]) {
            int j = stack.pop();
            res[j] = i - j;
        }
        // 【保持栈单调递减】第i天新温度不大于栈顶第j天温度，将第i天入栈
        stack.push(i);
    }
    return res;
}

public int trap(int[] height) {
    int res = 0;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < height.length; i++) {
        int h = height[i];
        // 【及时循环去掉无用数据，并更新结果】右墙柱子高度大于凹槽柱子高度，循环弹出栈顶凹槽柱子，并且结果加上由左墙、凹槽、右墙柱子计算得到的面积
        while (!stack.isEmpty() && height[stack.peek()] <= h) {
            int bottomH = height[stack.pop()];
            if (stack.isEmpty()) break; // 如果没有左墙柱子，直接结束该循环
            int left = stack.peek();
            int height = Math.min(height[left], height[i]) - bottomH; // 面积的高
            res += height * (i - left - 1);
        }
        // 【保持栈单调递减】
        stack.push(i);
    }
    return res;
}

public int largestRectangleArea(int[] heights) {
    // 预处理数组：前后补0
    int[] newHeights = new int[heights.length + 2];
    newHeights[0] = 0;
    System.arraycopy(heights, 0, newHeights, 1, heights.length);
    newHeights[newHeights.length - 1] = 0;
    Deque<Integer> stack = new LinkedList<>();
    int res = 0;
    for (int i = 0; i < newHeights.length; i++) {
        int h = newHeights[i];
        // 当当前高度小于栈顶高度时，触发面积计算
        while (!stack.isEmpty() && h < newHeights[stack.peek()]) {
            int height = newHeights[stack.pop()];
            int width = i - stack.peek() - 1; // 左边界为新栈顶索引，右边界为i
            res = Math.max(res, height * width);
        }
        stack.push(i);
    }
    return res;
}

class NumArray {
    private final int[] s;
    public NumArray(int[] nums) {
        s = new int[nums.length + 1];
        // 构造前缀和数组
        for (int i = 0; i < nums.length; i++) s[i + 1] = s[i] + nums[i];
    }
    public int sumRange(int left, int right) {
        return s[right + 1] - s[left];
    }
}

public int subarraySum(int[] nums, int k) {
    int n = nums.length;
    int[] s = new int[n + 1];
    // 构造前缀和数组
    for (int i = 0; i < n; i++) s[i + 1] = s[i] + nums[i];

    Map<Integer, Integer> cnt = new HashMap<>(); // 预分配空间
    int res = 0;
    for (int sj : s) {
        res += cnt.getOrDefault(sj - k, 0);
        cnt.put(sj, cnt.getOrDefault(sj, 0) + 1);
    }
    return res;
}

// 含义：将 sj 对应的值与 1 相加，如果不存在则初始值为 0
cnt.merge(sj, 1, Integer::sum);

class Solution {
    private int res;
    public int pathSum(TreeNode root, int targetSum) {
        // key：从根到 node 的节点值之和
        // value：节点值之和的出现次数
        // 注意在递归过程中，哈希表只保存根到 node 的路径的前缀的节点值之和
        Map<Long, Integer> cnt = new HashMap<>();
        cnt.put(0L, 1);
        backtrack(root, 0, targetSum, cnt);
        return res;
    }

    // s 表示从根到 node 的父节点的节点值之和（node 的节点值尚未计入）
    private void backtrack(TreeNode node, long s, int targetSum, Map<Long, Integer> cnt) {
        if (node == null) return;
        // 在递归过程中构建"前缀和数组"（这里没有用数组，而是用s动态存储）
        s += node.val;
        // 把 node 当作路径的终点，统计有多少个起点
        res += cnt.getOrDefault(s - targetSum, 0);

        cnt.merge(s, 1, Integer::sum); // cnt[s]++
        backtrack(node.left, s, targetSum, cnt);
        backtrack(node.right, s, targetSum, cnt);
        cnt.merge(s, -1, Integer::sum); // cnt[s]-- 恢复现场（撤销 cnt[s]++）
    }
}

class MinStack {
    // 注意不要使用 Stack 类，因为它继承自 Vector，是同步的，会导致一些性能问题
    private final Deque<int[]> st = new ArrayDeque<>();

    public MinStack() { // 初始化堆栈对象
        // 添加栈底哨兵 Integer.MAX_VALUE
        // 这里的 0 写成任意数都可以，反正用不到
        st.push(new int[]{0, Integer.MAX_VALUE});
    }

    public void push(int val) { // 将元素val推入堆栈
        st.push(new int[]{val, Math.min(getMin(), val)});
    }

    public void pop() { // 删除堆栈顶部的元素
        st.pop();
    }

    public int top() { // 获取堆栈顶部的元素
        return st.peek()[0];
    }

    public int getMin() { // 获取堆栈中的最小元素
        return st.peek()[1];
    }
}