LeetCode 135. Candy

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int candy(vector<int>& ratings) {
        const int n = ratings.size();
        vector<int> left(n);
        for (int i = 0; i < n; ++i)
            if (i > 0 && ratings[i] > ratings[i - 1])
                left[i] = left[i - 1] + 1;
            else
                left[i] = 1;
        int right = 0, ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (i < n - 1 && ratings[i] > ratings[i + 1])
                ++right;
            else
                right = 1;
            ans += max(left[i], right);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int candy(vector<int>& ratings) {
        const int n = ratings.size();
        int ans = 1, inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; ++i)
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ans += pre;
                inc = pre;
            } else {
                ++dec;
                if (dec == inc) ++dec;
                ans += dec;
                pre = 1;
            }
        return ans;
    }
};