Simple O(n) solution c++


  • 1
    Y
    class Solution {
    public:
        int candy(vector<int>& ratings) {
            if(ratings.size()==0) return 0;
            vector<int> candy(ratings.size(),1);
            for(int i=1;i<candy.size();i++) {
                if(ratings[i]>ratings[i-1]&&candy[i]<=candy[i-1])
                    candy[i]=candy[i-1]+1;
            }
            for(int i=candy.size()-2;i>=0;i--) {
                if(ratings[i]>ratings[i+1]&& candy[i]<=candy[i+1])
                    candy[i]=candy[i+1]+1;
            }
            return accumulate(begin(candy), end(candy), 0);
        }
    };

Log in to reply
 

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