首页 > itarticle > candy

candy

admin 11月 13, 2020 0

LeetCode 题目：candy 难度：hard

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

时间复杂度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
27
28
29
30
31
32
33
34
35
36
 
class  {
public:
    int candy(vector<int> &ratings) {
        if(ratings.size() <=1) return ratings.size();
        int index = 0;
        int pre = 1;
        int sum = 1;
        int gap = 0;
        for(int i = 1; i< ratings.size(); i++){
            if(ratings[i] < ratings[i-1]){
                if(pre <= 1){
                    if(gap > 1){
                        sum -= 1;
                        gap--;
                    }
                    sum += i - index;
                }
                if(pre > 2)
                    gap = pre -1;
                pre = 1;
                sum += pre;
            } else if(ratings[i] == ratings[i-1]){
                index = i;
                pre = 1;
                sum+=pre;
                gap = 0;
            }else {
                pre += 1;
                sum += pre;
                index = i;
                gap = 0;
            }
        }
        return sum;
    }
};
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能