儿童节吃个糖果！

利用拓扑排序求解约束性问题

Leetcode 135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

1
2
3

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

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

思路

本质上是一个约束性问题，约束条件比较简单：对于相邻节点u, v，两者之中rating值更大的，分到的糖果数量更大。即：dis(u) > = dis(v) + 1, if rating[u] > rating[v]。

并且这个关系是可以传递的，比如rating[u] > rating[v], rating[v] > rating[k]，那么 dis(u) > = dis[k] + 2。

所以这个时候就可以把这个关系抽象成一个有向图，对于每一个u而言，如果它的左右邻居rating值大于他，那么就构造一条边u → v。

对于图中任意一个链 u → v → x → y，由于 u 的入度为0，所以表明他前面不存在任何约束，即他可以分到最小的糖果数量 dis(u) = 1。那对于 v 而言，他前面有一个 u 约束，所以 dis[v] 一定是大于 dis[u] 的。由于题目要求最小值，所以 dis[v] = 2，依次类推。

所以，我们可以用拓扑排序模拟这个过程：首先建图并统计入度，然后依次将入度为0的加入队列进行排序（入度为0代表该节点没有约束了），每个节点更新自己子节点的dis。

代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> deg(n, 0), g[n];
        for (int i = 0;i < n;i++) {
            if (i > 0 && ratings[i] < ratings[i - 1]) {
                g[i].push_back(i - 1);
                ++deg[i - 1];
            }
            if (i < n - 1 && ratings[i] < ratings[i + 1]) {
                g[i].push_back(i + 1);
                ++deg[i + 1];
            }
        }
        deque<int> q;
        for (int i = 0;i < n;i++) {
            if (deg[i] == 0) q.push_back(i);
        }
        vector<int> dis(n, 1);
        while (q.size()) {
            int cur = q.front(); q.pop_front();
            for (int nxt : g[cur]) {
                dis[nxt] = dis[cur] + 1;
                if (--deg[nxt] == 0) q.push_back(nxt);
            }
        }
        return reduce(dis.begin(), dis.end(), 0);
    }
};

复杂度

时间：O(n)
空间：O(n)