leetcode 135： 分发糖果

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

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

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

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

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

提示：
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104

思路1：
贪心
从左右两个方向进行遍历，按照比前一个大就+1，否则就是1的原则。
最后取两次遍历的最大值即可。
主要思路参考链接：
链接1
链接2

class Solution:
    def candy(self, ratings: List[int]) -> int:
        left = [1] * len(ratings)
        right = [1] * len(ratings)
        res = 0
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                left[i] = left[i-1] + 1
        for j in range(len(ratings)-2, -1, -1):
            if ratings[j] > ratings[j+1]:
                right[j] = right[j+1] + 1
        for k in range(len(ratings)):
            res += max(left[k], right[k])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度O(n)，空间复杂度O(n)。

思路2：
降低时间复杂度，如果要求空间复杂度是O(1)。
主要参考了链接1的思路2：从左向右遍历一遍，如果大于前一个就+1，相等就是1，小于的话，记录当前递减的长度，再递减的时候，增加递减的长度的数量的糖果，这样就保证递减部分是满足要求的，但同时也要注意，当递减的长度和前面增的部分的糖果数量相同时，前面最后一个增的位置的糖果量需要加1，否则不满足要求。

class Solution:
    def candy(self, ratings: List[int]) -> int:
        res = 1
        pre, dec, inc = 1, 0, 1
        for i in range(1, len(ratings)):
            if ratings[i] >= ratings[i-1]:
                dec = 0
                if ratings[i] == ratings[i-1]:
                    pre = 1
                else:
                    pre += 1
                res += pre
                inc = pre
            else:
                dec += 1
                if dec == inc:
                    dec += 1
                res += dec
                pre = 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20