135. 分发糖果

题目描述

n 个孩子排成一行，输入数组 ratings，ratings[i] 是第 i 个孩子的评分。

要给每个孩子发糖，规则如下：每人至少 1 颗；对任意两个相邻的孩子，评分严格更高的那个必须拿得更多。评分相同的邻居之间没有要求。

返回满足规则时最少一共要发多少颗糖。

示例 1

输入：ratings = [1,0,2]
输出：5

解释：依次发 2、1、2 颗，共 5 颗。

示例 2

输入：ratings = [1,2,2]
输出：4

解释：依次发 1、2、1 颗，最后两人评分相同，第三人只需 1 颗。

数据范围

1 <= n == ratings.length <= 5 * 10^4
0 <= ratings[i] <= 5 * 10^4

解题思路：左右两次遍历

把规则拆成左、右两个方向。从左往右扫：若比左邻居高，left[i] = left[i-1] + 1，否则为 1。从右往左扫：若比右邻居高，right 加 1，否则重置为 1。每个孩子取 max(left[i], right)，同时满足两侧的要求，而且每一侧都是最小的必要值。

为什么正确

left[i] 是只考虑左侧规则时的最少糖数；反向扫到 i 时 right 是只考虑右侧规则时的最少糖数。

复杂度分析

时间 O(n)，空间 O(n)。

易错点

评分相等时没有约束，可以只给 1 颗；不能只做一遍扫描，否则下降段的要求会被漏掉。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        left = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                left[i] = left[i - 1] + 1
        total = left[n - 1]
        right = 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right += 1
            else:
                right = 1
            total += max(left[i], right)
        return total

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        Arrays.fill(left, 1);
        for (int i = 1; i < n; i++)
            if (ratings[i] > ratings[i - 1])
                left[i] = left[i - 1] + 1;
        int total = left[n - 1];
        int right = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1])
                right++;
            else
                right = 1;
            total += Math.max(left[i], right);
        }
        return total;
    }
}

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> left(n, 1);
        for (int i = 1; i < n; i++)
            if (ratings[i] > ratings[i - 1])
                left[i] = left[i - 1] + 1;
        int total = left[n - 1];
        int right = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1])
                right++;
            else
                right = 1;
            total += max(left[i], right);
        }
        return total;
    }
};

func candy(ratings []int) int {
	n := len(ratings)
	left := make([]int, n)
	for i := range left {
		left[i] = 1
	}
	for i := 1; i < n; i++ {
		if ratings[i] > ratings[i-1] {
			left[i] = left[i-1] + 1
		}
	}
	total := left[n-1]
	right := 1
	for i := n - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] {
			right++
		} else {
			right = 1
		}
		total += max(left[i], right)
	}
	return total
}

var candy = function(ratings) {
    const n = ratings.length;
    const left = new Array(n).fill(1);
    for (let i = 1; i < n; i++)
        if (ratings[i] > ratings[i - 1])
            left[i] = left[i - 1] + 1;
    let total = left[n - 1];
    let right = 1;
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1])
            right++;
        else
            right = 1;
        total += Math.max(left[i], right);
    }
    return total;
};

function candy(ratings: number[]): number {
    const n = ratings.length;
    const left: number[] = new Array(n).fill(1);
    for (let i = 1; i < n; i++)
        if (ratings[i] > ratings[i - 1])
            left[i] = left[i - 1] + 1;
    let total = left[n - 1];
    let right = 1;
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1])
            right++;
        else
            right = 1;
        total += Math.max(left[i], right);
    }
    return total;
}

载入编辑器，自己跑一遍 →

其他解法

两次遍历用 O(n) 数组，思路清晰易证；数坡法把空间降到 O(1)，但更难理解。

解法 2：常数空间数坡时间 O(n)，空间 O(1)

从左到右扫描，把评分序列看成上坡和下坡。上坡或持平时，当前孩子得 pre 个糖果，并用 inc 记录上坡长度。下坡时把下坡长度 dec 加 1，相当于给下坡上每个孩子多发一个。若 dec 追平 inc，坡顶也要多发一个，把坡顶并入下坡。

只用几个变量，一次遍历完成。状态含义较抽象，边界情形容易写错。

from typing import List

class Solution:
    def candy(self, ratings: List[int]) -> int:
        total, inc, dec, pre = 1, 1, 0, 1
        for i in range(1, len(ratings)):
            if ratings[i] >= ratings[i - 1]:
                dec = 0
                pre = 1 if ratings[i] == ratings[i - 1] else pre + 1
                total += pre
                inc = pre
            else:
                dec += 1
                if dec == inc:
                    dec += 1
                total += dec
                pre = 1
        return total

class Solution {
    public int candy(int[] ratings) {
        int total = 1, inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                total += pre;
                inc = pre;
            } else {
                dec++;
                if (dec == inc) dec++;
                total += dec;
                pre = 1;
            }
        }
        return total;
    }
}

class Solution {
public:
    int candy(vector<int>& ratings) {
        int total = 1, inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < (int)ratings.size(); i++) {
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                total += pre;
                inc = pre;
            } else {
                dec++;
                if (dec == inc) dec++;
                total += dec;
                pre = 1;
            }
        }
        return total;
    }
};

func candy(ratings []int) int {
	total, inc, dec, pre := 1, 1, 0, 1
	for i := 1; i < len(ratings); i++ {
		if ratings[i] >= ratings[i-1] {
			dec = 0
			if ratings[i] == ratings[i-1] {
				pre = 1
			} else {
				pre++
			}
			total += pre
			inc = pre
		} else {
			dec++
			if dec == inc {
				dec++
			}
			total += dec
			pre = 1
		}
	}
	return total
}

var candy = function(ratings) {
    let total = 1, inc = 1, dec = 0, pre = 1;
    for (let i = 1; i < ratings.length; i++) {
        if (ratings[i] >= ratings[i - 1]) {
            dec = 0;
            pre = ratings[i] === ratings[i - 1] ? 1 : pre + 1;
            total += pre;
            inc = pre;
        } else {
            dec++;
            if (dec === inc) dec++;
            total += dec;
            pre = 1;
        }
    }
    return total;
};

function candy(ratings: number[]): number {
    let total = 1, inc = 1, dec = 0, pre = 1;
    for (let i = 1; i < ratings.length; i++) {
        if (ratings[i] >= ratings[i - 1]) {
            dec = 0;
            pre = ratings[i] === ratings[i - 1] ? 1 : pre + 1;
            total += pre;
            inc = pre;
        } else {
            dec++;
            if (dec === inc) dec++;
            total += dec;
            pre = 1;
        }
    }
    return total;
}

贪心专题的其他题目

查看贪心全部题目 →