leetcode_solutions/Candy.cpp at master · shivangigoel1302/leetcode_solutions · GitHub

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
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int sum(int n){
        return (n*(n+1))/2;
    }
    int candy(vector<int>& ratings) {
        // int n = ratings.size();
        // vector<int>v(n,1);
        // for(int i = 1; i < n; i++){
        //     if(ratings[i] > ratings[i-1]){
        //         v[i] += v[i-1];
        //     }
        // }
        // for(int i = n-2; i >=0; i--){
        //     if(ratings[i] > ratings[i+1] && v[i] <= v[i+1]){
        //         v[i] = v[i+1]+1;
        //     }
        // }
        // int sum = 0;
        // for(int i = 0; i < n; i++){
        //     sum += v[i];
        // }
        // return sum;

        int candy = 0,up = 0, down = 0;
        int prevslope = 0;
        int n = ratings.size();
        for(int i = 1; i < n; i++){
            int currslope = ratings[i] > ratings[i-1] ? 1: ratings[i] < ratings[i-1] ? -1: 0;
            if((prevslope < 0 && currslope >= 0) || (prevslope > 0 && currslope == 0)){
                candy += sum(up) + sum(down) + max(up,down);
                up = 0;
                down = 0;
            }
            if(currslope > 0){
                up++;
            }
            else if(currslope < 0){
                down++;
            }
            else{
                candy++;
            }
            prevslope = currslope;
        }
        candy += sum(up) + sum(down) + max(up,down) + 1;
        return candy;
    }
};