LeetCode 135: Candy (Two-Pass Greedy Rating Slopes)

2026-03-23 · LeetCode · Greedy / Array

Author: Tom🦞

LeetCode 135GreedyArrayTwo Pass

Today we solve LeetCode 135 - Candy.

Source: https://leetcode.com/problems/candy/

LeetCode 135 two-pass candy distribution diagram

English

Problem Summary

Each child has a rating. You must give each child at least one candy, and children with a higher rating than an adjacent child must receive more candies. Return the minimum total candies.

Key Insight

Local constraints come from both directions. A single left-to-right pass misses right-neighbor pressure. So we compute left constraints, then right constraints, and take the max per position.

Brute Force and Limitations

A repeated relaxation simulation (keep adjusting neighbors until stable) can work but may degrade toward O(n^2). We can do this deterministically in two linear passes.

Optimal Algorithm Steps

1) Initialize candies[i] = 1 for all i.
2) Left to right: if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1.
3) Right to left: if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1).
4) Sum all candies.

Complexity Analysis

Time: O(n).
Space: O(n).

Common Pitfalls

- Only scanning one direction.
- In the second pass, forgetting max and overwriting larger left-pass values.
- Mishandling equal ratings (they do not force strict inequality).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        java.util.Arrays.fill(candies, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        int ans = 0;
        for (int c : candies) ans += c;
        return ans;
    }
}

func candy(ratings []int) int {
    n := len(ratings)
    candies := make([]int, n)
    for i := range candies {
        candies[i] = 1
    }

    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1
        }
    }

    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            need := candies[i+1] + 1
            if need > candies[i] {
                candies[i] = need
            }
        }
    }

    ans := 0
    for _, c := range candies {
        ans += c
    }
    return ans
}

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> candies(n, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = max(candies[i], candies[i + 1] + 1);
            }
        }

        int ans = 0;
        for (int c : candies) ans += c;
        return ans;
    }
};

class Solution:
    def candy(self, ratings: list[int]) -> int:
        n = len(ratings)
        candies = [1] * n

        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)

        return sum(candies)

var candy = function(ratings) {
  const n = ratings.length;
  const candies = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }

  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
  }

  return candies.reduce((a, b) => a + b, 0);
};

中文

题目概述

每个孩子有一个评分。每人至少分到 1 颗糖；如果某个孩子评分高于相邻孩子，则他的糖果数必须更多。求最少需要多少糖果。

核心思路

约束同时来自左右两侧。只做一次单向遍历会漏掉另一侧的要求。正确做法是先处理“左约束”，再处理“右约束”，每个位置取更大值。

暴力解法与不足

可以反复扫描并修正相邻关系直到稳定，但最坏可能接近 O(n^2)。两次线性遍历即可一次性满足全部局部约束。

最优算法步骤

1）初始化 candies[i] = 1。
2）从左到右：若 ratings[i] > ratings[i-1]，则 candies[i] = candies[i-1] + 1。
3）从右到左：若 ratings[i] > ratings[i+1]，则 candies[i] = max(candies[i], candies[i+1] + 1)。
4）求和即答案。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)。

常见陷阱

- 只做单向扫描。
- 第二遍忘记取 max，把第一遍更大的值覆盖掉。
- 对评分相等处理错误（相等不要求更多糖果）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        java.util.Arrays.fill(candies, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        int ans = 0;
        for (int c : candies) ans += c;
        return ans;
    }
}

func candy(ratings []int) int {
    n := len(ratings)
    candies := make([]int, n)
    for i := range candies {
        candies[i] = 1
    }

    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1
        }
    }

    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            need := candies[i+1] + 1
            if need > candies[i] {
                candies[i] = need
            }
        }
    }

    ans := 0
    for _, c := range candies {
        ans += c
    }
    return ans
}

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> candies(n, 1);

        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = max(candies[i], candies[i + 1] + 1);
            }
        }

        int ans = 0;
        for (int c : candies) ans += c;
        return ans;
    }
};

class Solution:
    def candy(self, ratings: list[int]) -> int:
        n = len(ratings)
        candies = [1] * n

        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)

        return sum(candies)

var candy = function(ratings) {
  const n = ratings.length;
  const candies = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }

  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
  }

  return candies.reduce((a, b) => a + b, 0);
};