135. Candy

題目 / Problem

中文： 有 n 個小孩站成一排，每個小孩有一個評分值 ratings[i]。你需要按以下規則分發糖果：

每個小孩至少要有 1 顆糖果。
評分比相鄰小孩高的，糖果數必須比那位相鄰小孩多。

回傳最少需要的糖果總數。

English: There are n children in a line, each with a rating value ratings[i]. Distribute candies so that:

Every child gets at least 1 candy.
A child with a higher rating than an immediate neighbor receives strictly more candies than that neighbor.

Return the minimum total number of candies needed.

Constraints: - n == ratings.length - 1 <= n <= 2 * 10^4 - 0 <= ratings[i] <= 2 * 10^4

Worked example: ratings = [1,0,2] → answer 5. One valid allocation is [2, 1, 2] (sum = 5). The first child has a higher rating than the second, so it needs more candy than the second; the third has a higher rating than the second, so it also needs more than the second.

名詞解釋 / Glossary

Greedy algorithm / 貪婪演算法：每一步做當下看起來最好的選擇，期望最終全域最優。本題的「左右各掃一遍取最大值」就是典型貪婪。 / Make the locally best choice at each step, hoping it leads to a global optimum. The "scan left, scan right, take max" idea here is a classic greedy.
Two-pass scan / 兩趟掃描：對陣列從左到右走一次、再從右到左走一次。每趟只處理一個方向的限制條件。 / Iterate the array once left→right and once right→left; each pass enforces the constraint from only one direction.
Invariant / 不變量：演算法執行過程中始終保持為真的性質。本題的不變量是「每趟掃描結束後，那個方向的相鄰大小關係已被滿足」。 / A property the algorithm keeps true at all times. Here: after each pass, the neighbor rule is satisfied in that scan's direction.
Auxiliary array / 輔助陣列：為了演算法方便而額外配置的陣列（不是輸入的一部分）。在 C 裡通常用 malloc 配置，用完要 free。 / An extra array allocated to help the algorithm. In C it's typically malloc'd and must be free'd.
malloc / free：C 的動態記憶體配置與釋放函式。malloc(n * sizeof(int)) 取得能放 n 個 int 的連續記憶體；free 把它還回去避免洩漏。 / C's heap allocation/release functions. malloc(n * sizeof(int)) gets memory for n ints; free returns it to prevent leaks.
std::vector / 向量容器：C++ 標準函式庫的動態陣列，會自動管理記憶體，支援 [] 隨機存取與 .size()。 / C++ STL dynamic array; manages memory automatically, supports [] indexing and .size().
std::max / 取最大值：標頭 <algorithm> 中的函式，回傳兩個值中較大者。 / Function from <algorithm> returning the larger of two values.

思路

最直覺的暴力解是反覆掃描整個陣列，只要發現某個小孩違反規則（評分比鄰居高卻沒拿到更多糖果），就把他的糖果加 1，直到所有規則都被滿足。這樣最壞情況下要掃 O(n) 次、每次 O(n)，總共 O(n²)，當 n = 2×10⁴ 時會過慢，而且邏輯也容易出錯。關鍵觀察是：每個小孩 i 其實只受兩種限制——「左邊鄰居 i-1 的評分比他低時，他要比左邊多」與「右邊鄰居 i+1 的評分比他低時，他要比右邊多」。這兩個方向彼此獨立，於是我們可以分開處理：先從左到右掃一遍，只考慮左鄰居條件，得到一個「左側需求」；再從右到左掃一遍，只考慮右鄰居條件，得到一個「右側需求」。最後每個位置取兩者的最大值，就能同時滿足兩個方向的限制。每趟掃描中只要 ratings[i] > ratings[i-1] 就讓 i 的糖果等於前一個 +1，否則重設為 1（最低要求）。為什麼這樣是最少？因為任一條件被違反時，多給 1 顆是必要且足夠的；取兩方向的最大值也只是恰好同時滿足兩邊。整體 O(n) 時間、O(n) 空間。

The brute-force idea — repeatedly sweep the array bumping any child who violates a rule by 1 candy — works but is O(n²) in the worst case and error-prone. The key insight: every child i is constrained by only two neighbors, and the "must beat left neighbor" rule and the "must beat right neighbor" rule are independent. So we split the problem into two passes. Left-to-right pass: for each i, if ratings[i] > ratings[i-1], set left[i] = left[i-1] + 1; otherwise reset to 1. After this pass, the left-neighbor rule is satisfied everywhere. Right-to-left pass: symmetrically build right[i]. Then the answer for child i is max(left[i], right[i]), and the total candy is the sum. Why is this the minimum? Each pass uses the smallest possible increment (just +1) when the rating strictly increases, and 1 (the floor) otherwise; taking the max merges both constraints without any slack. Total work is O(n) time and O(n) extra space.

逐步走查 / Walkthrough

Take ratings = [1, 0, 2] (n = 3).

Pass 1 — left to right (build left[], start each at 1):

i	ratings[i]	ratings[i-1]	condition	left[i]
0	1	—	base case	1
1	0	1	0 > 1? No → reset	1
2	2	0	2 > 0? Yes → left[1]+1	2

left = [1, 1, 2].

Pass 2 — right to left (build right[], start each at 1):

i	ratings[i]	ratings[i+1]	condition	right[i]
2	2	—	base case	1
1	0	2	0 > 2? No → reset	1
0	1	0	1 > 0? Yes → right[1]+1	2

right = [2, 1, 1].

Combine — candy[i] = max(left[i], right[i]):

i	left[i]	right[i]	max
0	1	2	2
1	1	1	1
2	2	1	2

Sum = 2 + 1 + 2 = 5. ✓

Solution — C

/*
 * Two-pass greedy / 兩趟貪婪：
 *   Pass 1 (L→R): ensure each child > left neighbor when its rating is higher.
 *   Pass 2 (R→L): ensure each child > right neighbor when its rating is higher.
 *   Answer = sum of max(left[i], right[i]).  O(n) time, O(n) space.
 */

#include <stdlib.h>   // malloc, free / 動態配置與釋放

int candy(int* ratings, int ratingsSize) {
    int n = ratingsSize;                       // 別名 n，方便閱讀 / alias for readability
    if (n <= 1) return n;                      // 0 或 1 個小孩直接回傳 / trivial cases: 0 or 1 child

    // 配置兩個輔助陣列，分別記錄左、右方向的需求
    // Allocate two helper arrays for the left-side and right-side requirements
    int* left  = (int*)malloc(sizeof(int) * n);   // 每個 int 4 bytes，共 n 個 / n ints on the heap
    int* right = (int*)malloc(sizeof(int) * n);   // 同上 / same

    // 第一趟：從左到右 / Pass 1: left to right
    for (int i = 0; i < n; i++) {
        // 如果不是第一個，且評分比左鄰居高，糖果就比左鄰居多 1
        // If not first and rating beats left neighbor, take left[i-1] + 1
        if (i > 0 && ratings[i] > ratings[i - 1]) {
            left[i] = left[i - 1] + 1;          // 嚴格遞增 / strict +1 over previous
        } else {
            left[i] = 1;                        // 否則重設為最低值 1 / otherwise reset to floor 1
        }
    }

    // 第二趟：從右到左 / Pass 2: right to left
    for (int i = n - 1; i >= 0; i--) {
        // 如果不是最後一個，且評分比右鄰居高，糖果就比右鄰居多 1
        // If not last and rating beats right neighbor, take right[i+1] + 1
        if (i < n - 1 && ratings[i] > ratings[i + 1]) {
            right[i] = right[i + 1] + 1;        // 從右邊累積 / accumulate from the right
        } else {
            right[i] = 1;                       // 否則重設為 1 / otherwise reset to 1
        }
    }

    // 加總每個位置兩方向需求的最大值，就能同時滿足兩個條件
    // Sum the max of the two directions at each index
    int total = 0;                              // 累加器 / running total
    for (int i = 0; i < n; i++) {
        int a = left[i];                        // 左方向需求 / left-side need
        int b = right[i];                       // 右方向需求 / right-side need
        total += (a > b) ? a : b;               // 三元運算子取較大者 / ternary picks the larger
    }

    free(left);                                 // 釋放配置的記憶體，避免洩漏 / free heap memory
    free(right);                                // 同上 / same
    return total;                               // 回傳最少糖果總數 / return the minimum total
}

Solution — C++

/*
 * Two-pass greedy / 兩趟貪婪：identical algorithm to the C version,
 * but using std::vector for automatic memory management and std::max
 * for clarity. O(n) time, O(n) space.
 */

#include <vector>      // std::vector 動態陣列 / dynamic array
#include <algorithm>   // std::max 取最大值 / max helper

class Solution {
public:
    int candy(std::vector<int>& ratings) {
        int n = static_cast<int>(ratings.size());   // 取大小，轉成 int 避免無號比較 / cast size_t→int
        if (n <= 1) return n;                       // 邊界：0 或 1 個小孩 / edge case

        // vector<int>(n, 1) 建立大小為 n、全部初始化為 1 的向量
        // vector<int>(n, 1) builds a length-n vector with every element = 1 (the floor)
        std::vector<int> left(n, 1);                // 左方向需求 / left-side needs
        std::vector<int> right(n, 1);               // 右方向需求 / right-side needs

        // 第一趟：左到右 / Pass 1: left to right
        for (int i = 1; i < n; ++i) {
            // 評分比左鄰居高 → 糖果至少多 1
            // Higher rating than left neighbor → at least one more candy
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;          // 在前一個基礎 +1 / +1 over previous
            }
            // 否則保持初始的 1 / otherwise keep the initial 1
        }

        // 第二趟：右到左 / Pass 2: right to left
        for (int i = n - 2; i >= 0; --i) {
            // 評分比右鄰居高 → 糖果至少多 1
            // Higher rating than right neighbor → at least one more candy
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;        // 從右側累積 +1 / +1 from the right
            }
        }

        // 把每個位置兩方向的最大值加起來
        // Sum max(left[i], right[i]) over all i
        int total = 0;                              // 總和 / running total
        for (int i = 0; i < n; ++i) {
            total += std::max(left[i], right[i]);   // std::max 取兩者較大者 / pick the larger
        }
        return total;                               // 最少糖果數 / minimum total candies
    }
};

複雜度 / Complexity

Time: O(n) — 共三趟 for 迴圈，每趟對 n 個位置做常數工作；n 是小孩數量。 / Three for-loops, each doing constant work per index over n elements; n is the number of children.
Space: O(n) — 額外配置兩個長度為 n 的輔助陣列存放左右方向的需求。 / Two auxiliary arrays of length n hold the per-direction requirements.

Pitfalls & Edge Cases

第一個 / 最後一個元素沒有對應方向的鄰居 / Boundary indices have no neighbor in one direction：第一趟必須從 i = 1 開始（或在 i == 0 時直接設 1），第二趟必須從 i = n-2 開始。漏掉這個檢查會讀到 left[-1] 或 right[n]，造成未定義行為。 / Pass 1 must guard i > 0 (or start at 1); pass 2 must guard i < n-1. Missing the guard reads out-of-bounds memory.
重設為 1 而非保留前一個值 / Reset to 1 when the rating doesn't strictly increase：只要 ratings[i] <= ratings[i-1] 就要把 left[i] 設為 1（最低值），不能繼續 +1。相等的評分不需要多給糖果——題目只要求「嚴格較高」者多。 / When ratings[i] <= ratings[i-1], reset to 1; equal ratings don't require more candy — the rule is strictly higher.
取最大值而不是相加 / Take max, not sum：合併兩方向時必須是 max(left[i], right[i])，不是 left[i] + right[i]，否則會嚴重多算。 / Combining the two passes uses max, not + — otherwise you double-count.
C 裡記得 free / Don't forget free in C：malloc 配置的記憶體不釋放會在多次測資中洩漏。C++ 的 vector 自動處理。 / malloc without free leaks across LeetCode's many test cases; vector handles this automatically.
整數溢位 / Integer overflow：n ≤ 2×10⁴，每人最多 n 顆糖果，總和上限約 4×10⁸，仍在 32-bit int 範圍內，但若題目放寬到更大 n 就要改 long long。 / n ≤ 2×10⁴ keeps the worst-case sum within 32-bit int, but a larger n would need long long.
n == 0 或 n == 1：題目保證 n ≥ 1，但仍建議顯式處理 n <= 1 以避免空配置或邊界邏輯錯誤。 / Constraints guarantee n ≥ 1, but handling n <= 1 explicitly keeps the code defensive.