LeetCode Candy：雙向掃描動態規劃分發糖果

LeetCode Candy：左右雙掃 DP

題目大意

N 個孩子排成一列，每人有評分 rating[i]。分糖規則：

1. 每人至少 1 顆。
2. 評分較高的孩子比相鄰孩子糖果多。

求最少總糖果數。

雙向掃描法

1. 左→右：candy[i] = 1 若 rating[i] ≤ rating[i-1]，否則 candy[i] = candy[i-1] + 1。保證左側條件。
2. 右→左：若 rating[i] > rating[i+1]，candy[i] = max(candy[i], candy[i+1] + 1)。修正右側條件，取最大值保證不破壞左側已滿足條件。
3. 累加 candy[]。

代碼

int candy(vector& ratings) {
    int n = ratings.size();
    vector candy(n, 1);
    for (int i=1;i=0;i--)
        candy[i] = ratings[i] <= ratings[i+1] ? candy[i] : max(candy[i], candy[i+1]+1);
    return accumulate(candy.begin(), candy.end(), 0);
}

複雜度

時間 O(N)，空間 O(N)（可優化至 O(1) 額外空間）。