LeetCode 135. Candy

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 135. Candy 原题链接困难

作者：

wzc1995 , 2018-05-30 14:03:39 , 所有人可见 , 阅读 2470

8

4

题目描述

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

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

每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

样例

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

算法1

(优先队列) $O(n \log n)$

可以按照排名值最低的孩子开始分配，用优先队列保存所有孩子的排名值和其位置。
每次取出一个孩子的排名值和位置时，通过一系列分类讨论，判断需要如何分配糖果。
具体地，可以分为左右均未分配和已分配两大类情况，分类讨论的过程这里不再赘述。

时间复杂度

用堆来管理，时间复杂度为 $O(n\log n)$。

空间复杂度

需要 $O(n)$ 的额外空间存储答案和队列。

C++ 代码

class Solution {
public:
    #define PI pair<int, int>
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        if (n == 1)
            return 1;

        priority_queue<PI, vector<PI>, greater<PI>> heap;

        vector<int> candies(n, 0);
        int ans = 0;
        for (int i = 0; i < n; i++)
            heap.push(make_pair(ratings[i], i));

        while (!heap.empty()) {
            PI sta = heap.top();
            int val = sta.first, i = sta.second;
            heap.pop();
            if (i == 0) {
                if (candies[1] == 0 || val == ratings[1])
                    candies[0] = 1;
                else
                    candies[0] = candies[1] + 1;
            }
            else if (i == n - 1) {
                if (candies[n - 2] == 0 || val == ratings[n - 2])
                    candies[n - 1] = 1;
                else
                    candies[n - 1] = candies[n - 2] + 1;
            }
            else {
                if (candies[i - 1] == 0 && candies[i + 1] == 0)
                    candies[i] = 1;
                else if (candies[i - 1] == 0 && candies[i + 1] != 0) {
                    if (val == ratings[i + 1])
                        candies[i] = 1;
                    else
                        candies[i] = candies[i + 1] + 1;
                }
                else if (candies[i - 1] != 0 && candies[i + 1] == 0) {
                    if (val == ratings[i - 1])
                        candies[i] = 1;
                    else
                        candies[i] = candies[i - 1] + 1;
                }
                else {
                    if (val == ratings[i - 1] && val == ratings[i + 1])
                        candies[i] = 1;
                    else if (val > ratings[i - 1] && val == ratings[i + 1])
                        candies[i] = candies[i - 1] + 1;
                    else if (val == ratings[i - 1] && val > ratings[i + 1])
                        candies[i] = candies[i + 1] + 1;
                    else
                        candies[i] = max(candies[i - 1], candies[i + 1]) + 1;
                }
            }
            ans += candies[i];
        }
        return ans;
    }
};

算法2

(线性扫描) $O(n)$

现在我们尝试按位置从前到后逐一分析每个位置需要分配多少糖果。
对于 $0 < i < n-1$，根据前一个位置和后一个的大小关系，可以分为9种情况：123、122、121、223、222、221、323、322、321，数字代表三个位置的相对大小。
定义三个变量，last记录上一个位置分配的糖果数，down_size 记录已经有多少次排名连续向下，last_summit 记录上一次连续向上的巅峰是多少。
接下来通过代码注释讨论这 9 种情况对应的分配方式。

时间复杂度

由于只进行一次线性扫描，故时间复杂度为 $O(n)$。

空间复杂度

仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        if (n == 1)
            return 1;

        if (n == 2)
            return ratings[0] == ratings[1] ? 2 : 3;

        int ans = 0, last = 0, down_size = 0, last_summit = n + 1;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                int v = ratings[i], rv = ratings[i + 1];
                if (v < rv) {
                    ans += 1;
                    last = 1;
                }
                else if (v == rv) {
                    ans += 1;
                }
                else if (v > rv) {
                    down_size = 1;
                }
            }
            else if (i == n - 1) {
                int lv = ratings[i - 1], v = ratings[i];
                if (lv < v) {
                    ans += last + 1;
                }
                else if (lv == v) {
                    ans += 1;
                }
                else {
                    ans += (down_size + 2) * (down_size + 1) / 2;
                    if (down_size + 2 > last_summit)
                        ans += down_size - last_summit + 2;
                }
            }
            else {
                int lv = ratings[i - 1], v = ratings[i], rv = ratings[i + 1];
                if (lv < v) {
                    if (v < rv) {
                        // 情况 123，此时只要根据将i位置分配 last+1 个糖果即可。
                        // 同时必须更新 last，因为之后是 1 开头的情况。

                        ans += last + 1;
                        last++;
                    }
                    else if (v == rv) {
                        // 情况 122，将 i 位置分配 last+1 个糖果。
                        // 但可以不管 last，因为之后是 2 开头的情况。

                        ans += last + 1;
                    }
                    else {
                        // 情况 121，这里比较复杂，首先将 i 位置分配 last+1 个糖果。
                        // 因为出现了顶峰，需要记录顶峰的高度，为之后 3 下降的情况做准备。
                        // 同时默认 down_size 还没有开始，为 0。

                        ans += last + 1;
                        last_summit = last + 1;
                        down_size = 0;
                    }
                }
                else if (lv == v) {
                    if (v < rv) {
                        // 情况 223，这里直接分配 1 个糖果即可。
                        // 需要更新 last 为 1 为之后 1 开头的情况做准备。

                        ans += 1;
                        last = 1;
                    }
                    else if (v == rv) {
                        // 情况 222，分配 1个糖果。
                        // 但可以不管 last，因为之后是 2 开头的情况。

                        ans += 1;
                    }
                    else {
                        // 情况 221，此时还不确定需要分配多少糖果。
                        // 因为后边是 3 下降的情况，需要等下降到最底部才能确定。
                        down_size = 1;
                    }
                }
                else {
                    if (v < rv) {
                        // 情况 323，此时出现了一个低谷，
                        // 需要补全在 221 或 321 中出现的不确定的糖果数。
                        // 此时 down_size 记录了不确定的数量，直接进行等差数列求和即可。

                        ans += (down_size + 2) * (down_size + 1) / 2;

                        // 这里需要特别处理 121 的情况。
                        // 由于在 121 中，我们擅自将最高峰设置为了 last+1，这里需要进行补救。
                        // 如果上一段上升时的长度小于这一段下降的长度，
                        // 则需要将最高峰的糖果数增加相应的值。

                        if (down_size + 2 > last_summit)
                            ans += down_size - last_summit + 2;

                        // 清空上一次最高峰的值。
                        last_summit = n + 1;

                        // 同时需要更新 last，为之后 1 开头情况做准备。
                        last = 1;
                    }
                    else if (v == rv) {
                        // 情况 322，同理情况 323，但不需要更新 last。

                        ans += (down_size + 2) * (down_size + 1) / 2;
                        if (down_size + 2 > last_summit)
                            ans += down_size - last_summit + 2;
                        last_summit = n + 1;
                    }
                    else {
                        // 情况 321，连续下降，直接累计下降长度。
                        down_size += 1;
                    }
                }
            }
        }
        return ans;
    }
};

算法3

(图论) $O(n)$

我们可以把这个问题建模成图论问题。
假设每个位置都是一个点，如果相邻两个点的 ratings 不等，则从 ratings 较小的点向较大的点连一条边权为 1 的边。
假设我们有一个超级源点 S，向每个位置都连接了边权为 1 的边，求从 S 到每个点的最长路。共有 n + 1 个点，最多有 2n - 1 条边。
这里相当于求带负权边的最短路，只能用 Bellman-Ford 求解，但 Bellman-Ford 的理论时间复杂度为 $O(nm)$。
我们发现，第 0 轮 Bellman-Ford 迭代会将全部 n 个点的距离更新为 1。所以我们就可以当做求每个点初值为 1 的最长路。
接下来，每个点的度数不超过 2，且边都是连向了左右邻居，所以我们可以仅用额外两轮迭代完成整个图的更新。
第 1 轮迭代，从点 0 到点 n-1 更新；第 2 轮迭代，从点 n-1 到点 0 更新。

时间复杂度

两轮线性扫描，故时间复杂度为 $O(n)$。

空间复杂度

需要 $O(n)$ 的额外空间存储答案。

C++ 代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> candies(n, 1);

        for (int i = 0; i < n - 1; i++)
            if (ratings[i + 1] > ratings[i])
                candies[i + 1] = candies[i] + 1;

        for (int i = n - 1; i >= 1; i--)
            if (ratings[i - 1] > ratings[i] && candies[i - 1] <= candies[i])
                candies[i - 1] = candies[i] + 1;

        int ans = 0;
        for (int x : candies)
            ans += x;

        return ans;
    }
};

4 评论

Komorebi 2020-05-07 16:31

class Solution {
public:
//先一人分一个，然后从左往右遍历，加，然后从右往左遍历，再加
int candy(vector[HTML_REMOVED]& ratings) {
int n=ratings.size();
if(ratings.empty()) return 0;
vector[HTML_REMOVED] candys(n,1);
int sum=0;
for(int i=1;i[HTML_REMOVED]ratings[i-1]) candys[i]=candys[i-1]+1;
}
for(int i=n-2;i>=0;i–)
{
if(ratings[i]>ratings[i+1]&&candys[i]<=candys[i+1])
candys[i]=candys[i+1]+1;
}
for(auto x:candys)
sum+=x;
return sum;
}