135. Candy
HardDescription
n個孩子站成一排，每人有一個評分ratings[i]。你需要分配糖果，規則：每人至少 1 顆；相鄰兩人中評分較高的必須拿到更多糖果。回傳所需的最少糖果總數。
Example:
Input: ratings = [1,0,2] Output: 5 (分配 [2,1,2])
Intuition#
兩次遍歷：先從左到右處理右邊比左邊大的情況，再從右到左處理左邊比右邊大的情況。
- 單方向遍歷無法同時滿足左右兩邊的約束
- 從左到右：如果
ratings[i] > ratings[i-1]，則candy[i] = candy[i-1] + 1 - 從右到左：如果
ratings[i] > ratings[i+1]，則candy[i] = max(candy[i], candy[i+1] + 1) - 取兩次的最大值確保兩個方向的約束都滿足
Approaches#
1: 兩次遍歷#
- 概念: 第一次從左到右確保右鄰比左鄰大時糖果更多，第二次從右到左確保左鄰比右鄰大時糖果更多。
- 時間複雜度:
O(n) - 空間複雜度:
O(n)
class Solution {
fun candy(ratings: IntArray): Int {
val n = ratings.size
val candies = IntArray(n) { 1 }
// 從左到右
for (i in 1 until n) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1
}
}
// 從右到左
for (i in n - 2 downTo 0) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = maxOf(candies[i], candies[i + 1] + 1)
}
}
return candies.sum()
}
}⭐2: 一次遍歷（斜坡計數）#
- 概念: 追蹤上升和下降斜坡的長度。上升時糖果遞增；下降時回頭補糖果。
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun candy(ratings: IntArray): Int {
val n = ratings.size
if (n <= 1) return n
var total = 1
var up = 0
var down = 0
var peak = 0
for (i in 1 until n) {
when {
ratings[i] > ratings[i - 1] -> {
up++
down = 0
peak = up
total += up + 1
}
ratings[i] < ratings[i - 1] -> {
down++
up = 0
// 如果下降長度超過峰值，峰值也需要加 1
total += down + if (down > peak) 1 else 0
}
else -> {
up = 0
down = 0
peak = 0
total += 1
}
}
}
return total
}
}🔑 Takeaways#
- Pattern: 雙向貪心 — 分別處理左右約束，取最大值合併
- 關鍵技巧: 兩次遍歷（左到右 + 右到左）是處理「相鄰元素雙向約束」的經典模式；一次遍歷需要追蹤斜坡和峰值