0(n) time? 0(1) space?


  • 0
    A
    class Solution {
    public:
        int candy(vector<int> &ratings) {
    	int i,j,k;
    	if(ratings.size() == 0) return 0;
    	int sum = 1;
    	int cnum = 1;
    	int old_cnum = 1;
    	bool old_add = true;
    	j = 0;
    	for(i = 1; i < ratings.size(); i++){
    	    if(ratings[i] < ratings[i-1]){
    		if(cnum == 1){
    		    if(old_add || i - j < old_cnum - 1)
    			sum = sum + (i - j) + 1;
    		    else
    			sum = sum + (i - j) + 2;
    		}
    		else{
    		    old_cnum = cnum;
    		    cnum = 1;
    		    sum = sum + cnum;
    		    j = i;
    		}
    	    }
    	    else if(ratings[i] == ratings[i-1]){
    		old_add = true;
    		cnum = 1;
    		sum = sum + cnum;
    		j = i;
    	    }
    	    else{
    		old_add = false;
    		cnum++;
    		sum = sum + cnum;
    	    }
    	}
    	return sum;
        }
    };

Log in to reply
 

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