发糖果(Leetcode 135)

发表于 | 分类于 ， | | 本文总阅读数 次
| 字数统计: 1.7k | 阅读时长 ≈ 6
Leetcode 135

1

题目分析

  题目的描述非常简单，但是题目的难度比较大，这里没有告诉我们题目的数据范围，但是我在提交时超时了，其中超时的数据有20000个，因此要想出比$O(n^2)$更小的时间复杂度。

遍历

我们要求相邻的孩子中评分高的获得更多的糖果，这句话包含了两层意思，如果比前面的人评分高，那么必须比他的糖果数多，如果比后面的人评分高，那么必须比他的糖果数多。为了保证糖果数量最少，那么我们就比他多一个即可。

因此我们可以先和前面的人比较，如果ratings[i] > ratings[i - 1]，说明比前面那个人评分高，则res[i] = res[i - 1] + 1，否则给这个人分配一个糖果即可，res[i] = 1。遍历完成后，我们得到了满足比前面孩子评分高获得更多糖果的要求。

**然后还要和后面的人比较，如果ratings[i] > ratings[i + 1]，说明比后面那个人评分高，则res[i] = max(res[i], res[i + 1] + 1)**。为什么这一次稍微麻烦了一些呢？是因为要同时满足两边的要求，第i个孩子满足比前面评分高的糖果数最低为res[i]，满足比后面评分高的糖果数最低为res[i + 1] + 1，同时满足就是两者取最大值。两次遍历后得到的res数组就是最优的分配方案。要求糖果数可以在第二次遍历时求和，也可以进行第三次遍历，对res数组求和。

有的小朋友就会有疑问，会不会在第二次遍历时影响到第一次遍历的结果，导致不满足评分比前面的高，分到的糖果多呢？这是不会的，小伙伴担心的是这种情况，例如1354321。第一次遍历后，糖果的分配应该是1231111。小伙伴们担心第二次遍历时第四个孩子会不会在分配时超过第三个孩子。这是有可能发生的，但是发生后还会被第三个孩子超过。当第二次从后向前遍历到第四个孩子时的分配情况是这样的1234321。这时遍历到第三个孩子，因为第三个孩子比第四个孩子评分高，因此还会做res[2] = max(res[2], res[3] + 1)。这样第三个孩子又会超过第四个孩子。最优解应该是1254321。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

优化遍历

上面的算法比较容易理解，代码写起来也非常简单和美观，推荐小伙伴们使用第一种算法。

第二种算法是一个拓展，希望小伙伴们了解即可。

我们将孩子看成一个山峰，其中上坡的高度记为inc，下坡的高度记为dec。上坡高度指该同学左边最近的一次连续上升数量。如12321，那么3的上坡高度就是3，因为1<2<3，上坡高度k也指这个孩子应该分发的个数。因为上坡的起点可以分发1个糖果，那么上坡高度就是分发k个糖果。这和第一种算法的前半部分是类似的。

我们现在关心下坡的情况。下坡是指该同学连续下降次数，但是下坡不包括山顶元素，如12321，在3这个时候，上坡高度为3，然后开始下坡，到达2时，下坡高度为1，到达末尾时，下坡的高度是2。

**假如下坡的高度是k，下坡时，有两种情况。

  1. 如果下坡的高度小于上坡的高度，那么我们就从1加到k即可。如13543，到达4时下坡高度为1，说明，可以给评分为4的孩子1个糖果，到达3时，下坡高度为2，此时糖果总数+2，可理解为将评分为4的孩子的糖果给评分为3的孩子，然后给评分为4的孩子两个糖果。即糖果向后移动一个。
  2. 如果下坡的高度大于上坡的高度，如1354321。到达3时，下坡高度为2，糖果数+2。到达2时，下坡高度为3，这样就会产生一些问题，如果将评分为3孩子的一个糖果给评分为2的孩子，评分为4的孩子的两个糖果给评分为3的孩子，再给评分为4的孩子3个糖果，就会错误。因为此时评分为5的孩子也是3个糖果，评分为4的孩子也是3个糖果。不满足评分高的孩子糖果数多。那么当上坡高度等于下坡高度时，我们就要额外给山顶的孩子一个糖果，让他高于右边的孩子。此时到达2时应该+4，而不是+3。这样的分配方案就是124321。然后最后一个评分为1的孩子，将4321向后移动，加上一个5给山顶的孩子**。

小伙伴们可以拿起笔和纸绘制一下这个过程，理清楚以后还是比较清晰的。可以配合这代码一起看。

在这个过程中，我们只需要判断处在上升还是下降过程中，记录上坡高度，下坡高度，第i个孩子前面那个孩子的糖果数即可。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<vector>

using namespace std;

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

刷题总结

  这个题目我推荐小伙伴们使用第一种算法，第二种算法比较绕，也难以想到。第一次做这个题目的小伙伴可能会被难住，多做一些题目，多见识一些方法就会更加得心应手。在笔试中遇到原题的概率相对较少，但是在面试中经常会遇到原题，因此多做题是非常有必要的。

-------------本文结束感谢您的阅读-------------
0%