My 40ms cpp solution with O(n) complexity


  • 0
    L
    class Solution {
    public:
        int candy(vector<int>& ratings) {
            int n = ratings.size(), sum = 0;
            vector<int> left(n, 0);
            vector<int> right(n, 0);
            for(int i = 0; i < n; i++){
                if(i - 1 >= 0 && ratings[i - 1] < ratings[i]) left[i] = left[i - 1] + 1;
                else left[i] = 1;
                int j = n - 1 - i;
                if(j + 1 < n && ratings[j + 1] < ratings[j]) right[j] = right[j + 1] + 1;
                else right[j] = 1;
            }
            for(int i = 0; i < n; i++){
                sum += (left[i] > right[i]) ? left[i] : right[i];
            }
            return sum;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.