LeetCode

LeetCode 45 跳跃游戏二

LeetCode 45 跳跃游戏二

中等偏下

https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150

这是一个关于分发糖果的算法问题，属于贪心算法范畴。下面给出 Java 版本的解法。

问题分析

  1. 每个孩子至少分到 1 个糖果。
  2. 相邻两个孩子中，评分更高的孩子必须获得更多糖果。
  3. 在满足上述条件的前提下，糖果总数要最少。

解决思路

  1. 从左到右遍历，保证右边评分更高的孩子比左边多一个糖果。
  2. 从右到左遍历，保证左边评分更高的孩子比右边多一个糖果。
  3. 对每个位置取两次遍历结果的较大值，再求和得到答案。

Java 代码实现 

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n == 0) return 0;

        int[] left = new int[n];
        int[] right = new int[n];

        // 从左到右遍历，确保右边高分孩子比左边多
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }

        // 从右到左遍历，确保左边高分孩子比右边多
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            } else {
                right[i] = 1;
            }
        }

        // 取两次遍历的最大值求和
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.max(left[i], right[i]);
        }

        return sum;
    }
}

代码解释

  1. 创建两个数组 left 和 right，分别记录从左到右、从右到左的最小糖果分配结果。
  2. 第一次遍历处理“右边评分更高”的约束。
  3. 第二次遍历处理“左边评分更高”的约束。
  4. 每个位置取两者较大值，累加后得到最少糖果数。

复杂度分析

  • 时间复杂度：O(n)，共三次线性遍历。
  • 空间复杂度：O(n)，使用了两个辅助数组。
© 2026 我的博客