【每日算法Day 69】面试经典题:分发糖果问题

题目链接

LeetCode 135. 分发糖果[1]

题目描述

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

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

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

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

示例1

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

      

示例2

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

      

题解

这题虽然难度定义成困难,但其实代码不长,思路也比较简单清晰。

首先明确一下题目中的两个条件,我们可以把所有人的分数在坐标轴中连起来,这样就形成了一个波形图(图片来自官方题解):

v2-f60d1385c7bbcdaacee85c6a6a957b68_b.jpg


那么这就像一座一座山峰一样,在谷底(左右两边分数都大于等于它)糖果数一定是 1 。从谷底往两侧扩展,糖果数逐渐加 1 就行了。

要注意的一点是图中 pt.13 那个位置也是一个谷底,因为它右边的分数等于它。

那么问题的关键就是如何找到这些谷底了。

两次遍历

首先初始化所有人都分到 1 个糖果。

然后从左向右遍历一次所有分数,如果发现分数小于等于前一个人分数,那暂时不用管,因为你从左向右是没法知道下坡的点距离谷底还有多远的。而如果发现分数大于前一个人分数,那么就在前一个人糖果数基础上,再多分一个给他,因为是上坡,所以谷底一定在左边已经遍历过了,是知道距离的。

接着就是遍历下坡了,也就是从右向左遍历所有分数,同理如果发现分数大于后一个人分数,那么就在后一个人糖果数基础上,再多分一个给他。

但是这里要处理一个冲突,那就是峰顶既是上坡,又是下坡,其实只要两次遍历完取上坡和下坡中糖果数较大的那个就行了。

总结一下就是一次从左向右遍历所有上坡,一次从右向左遍历所有下坡,峰顶取两次较大值

时间复杂度 O(n) ,空间复杂度 O(n)

一次遍历

从上面方法中可以看出,本题求解的难点就在于从左向右遍历的时候,下坡到底有多长没法知道,必须全部遍历完了才能知道。还有就是山峰的值必须看左右两边的上坡下坡有多长。

为了解决这个问题,我们可以用变量 up 记录上坡的长度,down 记录下坡的长度。

当遇到谷底的时候,就表明一座山遍历结束了,那么我们只需要比较 updown 的大小就知道峰顶取值了。

而如何判断一座山遍历结束呢?假设现在遍历到了第 i 个学生,我们再用两个变量,ns 表示 i-1i 的变化趋势(1:上升,-1:下降,0:不变),os 表示前一个时刻 i-2i-1 的变化趋势。那么谷底只有下面三种情况:

  • 。也就是前一个时刻在下降,当前时刻上升了,那显然第 i-1 个学生是谷底。
  • 。也就是前一个时刻在下降,当前时刻不变,这种情况下第 i-1 个学生也是谷底,因为根据题意,他的糖果数没必要比第 i 个学生多。
  • 。也就是前一个时刻在上升,当前时刻不变。这种情况下,山峰只有上坡(到峰顶 i-1 结束),没有下坡,所以这座山也遍历结束了,得计算糖果数了。

这座山峰的的糖果数可以表示为三部分之和:上坡、下坡和峰顶。上坡就是 ,下坡就是 ,峰顶就是 。算完了之后,这座山峰就再也不用考虑了, updown 都清零。

在具体实现的时候,这个方法细节有点多,一不小心就会错,直接看代码注释吧。

继续看下面这张图:

v2-f60d1385c7bbcdaacee85c6a6a957b68_b.jpg

贴一段官方的样例解释:

v2-be70e4bcf9709e45abe0b310bbccce90_b.jpg


时间复杂度 O(n) ,空间复杂度 O(1)

单调栈

我们用一个单调栈来保存单调下降的得分,也就是下坡。

当遍历到第 i 个学生时,如果栈顶元素 j 的得分小于等于 i 的得分,也就是遇到谷底了,那么就出栈,直到栈空。

最后用一个很大的数将栈里所有元素顶出来就行了。

时间复杂度 O(n) ,空间复杂度 O(n)

小结

第一种解法最容易理解和实现,也不用考虑什么特殊情况。但是后两种方法处理起来就稍稍有点麻烦了,需要结合样例和代码来理解。但是本质上都是一样的,都是从谷底(糖果数为 1)开始,向两周扩展。方法一是先从每个谷底向右边上坡扩展,再向左边下坡扩展。方法二是计算出相邻两个谷底之间的上坡下坡长度,然后直接计算。第三个方法是从每个谷底先向左边下坡扩展,再向右边上坡扩展。

代码

两次遍历(c++)

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

      

一次遍历(c++)

        class Solution {
public:
    int count(int n) {
        return n*(n+1)/2;
    }

    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int sum = 0;
        int up = 0, down = 0;
        int os = 0, ns = 0;
        for (int i = 1; i < n; ++i) {
            ns = ratings[i]>ratings[i-1] ? 1 : (ratings[i]<ratings[i-1] ? -1 : 0);
            // 这座山峰遍历结束,计算糖果数。             if ((os < 0 && ns >= 0) || os > 0 && ns == 0) {
                // 这里看似好像峰顶没有加 1,其实是 count(down) 减去了 1。                 // 因为谷底是共享的,所以将谷底给了下一座山峰的上坡。                 sum += count(up) + count(down) + max(up, down);
                up = down = 0;
            }
            if (ns > 0) up++;
            else if (ns < 0) down++;
            // 如果是平原,说明谷底不会共享,之前少加的 1 再补上。             else if (!ns) sum++;
            os = ns;
        }
        // 最后一座山峰循环里不会计算到,再加上。         sum += count(up) + count(down) + max(up, down) + 1;
        return sum;
    }
};

      

单调栈(c++)

        class Solution {
public:
    int candy(vector<int>& ratings) {
        ratings.push_back(INT_MAX);
        int n = ratings.size();
        vector<int> res(n, 1);
        stack<int> st;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            if (!st.empty() && ratings[i] >= ratings[st.top()]) {
                while (!st.empty()) {
                    int j = st.top();
                    st.pop();
                    if (j < n-1 && ratings[j] > ratings[j+1]) {
                        res[j] = max(res[j], res[j+1]+1);
                    }
                    if (j > 0 && ratings[j] > ratings[j-1]) {
                        res[j] = max(res[j], res[j-1]+1);
                    }
                    sum += res[j];
                }
            }
            st.push(i);
        }
        return sum;
    }
};

      

参考资料

[1]

LeetCode 135. 分发糖果: leetcode-cn.com/problem

算法码上来 文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。

全部评论

相关推荐

最讨厌装boyi的二🔥:服从性测试😉
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务