Cinte's Leetcode Record
0%

135. 分发糖果

Posted on Edited on In Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

135. 分发糖果

两次遍历，先从左往右再从右往左。

从左往右遍历时候保证了只要是当前得分大于他左边的得分，他的值就会比他左边的大。从右往左，当遇见当前得分大于右边得分时候，对当前的值判断，如果本身就符合，那就无所谓，如果不符合，就是max(右边+1,本身)，所以不会破坏左边遍历的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> nums(n);
        nums[0] = 1;
        for(int i = 1; i < n; ++i)
            nums[i] = ratings[i] > ratings[i - 1] ? nums[i - 1] + 1 : 1;
        for(int i = n - 2; i >= 0; --i)
            if(ratings[i] > ratings[i + 1] && nums[i] <= nums[i + 1])
                nums[i] = nums[i + 1] + 1;
        return accumulate(nums.begin(), nums.end(), 0);
    }
};

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
class Solution {
public:
    int candy(vector<int>& ratings) {
        int pre = 1, inc = 1 , dec = 0, ret = 1; // 要假设一开始是在升序的
        for(int i = 1, n = ratings.size(); i < n; ++i)
        {
            if(ratings[i] >= ratings[i - 1])
            {
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1; // 相等时候其实没影响，既不会像当前>左边导致当前要比左边高，也不会像当前>右边使得当前必须抬高来容纳右边
                ret += pre;
                inc = pre;
                dec = 0;
            }else
            {
                ++dec;
                if(dec == inc) // 不然再抬高就要把之前升序的末尾给超过了
                    ++dec;
                ret += dec;
                pre = 1; // 降序的末尾永远是1
            }
        }
        return ret;
    }
};