Easy understand O(n) time O(n) size cpp solution


  • 0
    Z
    class Solution {
    public:
    int candy(vector<int>& ratings) {
    	int size = ratings.size();
    	if(size==0)
    		return 0;
    	
        vector<int> leftToRight(size);
        vector<int> rightToLeft(size);
    	int sum = 0;
    	
    	leftToRight[0] = 1;
    	for(int i=1;i<size;i++){
    		if(ratings[i]>ratings[i-1])
    			leftToRight[i] = leftToRight[i-1]+1;
    	
    		else
    			leftToRight[i] = 1;
    	}
    	
    	sum+=leftToRight[size-1];
    	rightToLeft[size-1] = 1;
    	for(int i=size-2;i>=0;i--){
    		if(ratings[i]>ratings[i+1])
    			rightToLeft[i] = rightToLeft[i+1]+1;
    	
    		else
    			rightToLeft[i] = 1;
    		
    		sum+=(leftToRight[i]>rightToLeft[i]?leftToRight[i]:rightToLeft[i]);
    	}
    	return sum;
    }
    };

Log in to reply
 

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