C++ O(n) time and space AC solution


  • 0
    P
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        std::vector<int> vec(n, 1);
        int res = n;
        
        for(int i=1; i< n; i++){
            if(ratings[i] > ratings[i-1]){
                if(vec[i] <= vec[i-1]){
                    vec[i] = vec[i-1]+1;
                }    
            }
        }
        
        for(int i=n-1; i >= 1; i--){
            if(ratings[i-1] > ratings[i]){
                if(vec[i-1] <= vec[i]){
                    vec[i-1] = vec[i]+1;
                }    
            }
        }
        
        return std::accumulate(vec.begin(), vec.end(), 0);
    }

Log in to reply
 

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