O(n) time, O(1) space of C++ solution


  • 2
    S
    class Solution {
        public:
            int candy(vector<int>& ratings) {
            	if (ratings.empty())
            		return 0;
            	int ret = 1;
            	int prevCandy = 1;
            	for (int i = 1; i < ratings.size(); ++i){
            		if (ratings[i] > ratings[i - 1]){
                		++prevCandy;
                		ret += prevCandy;
            		}
            		else if (ratings[i] == ratings[i - 1]){
            			ret += 1;
            			prevCandy = 1;
            		}
            		else{
            			int count = 0;
            			while (i < ratings.size() && ratings[i] < ratings[i - 1]){
            				++count;
            				++i;
            			}
            			--i;
            			ret += max(count + 1, prevCandy) - prevCandy;
            			for (int j = count; j > 0; --j)
            				ret += j;
        			    prevCandy = 1;
            		}
            	}
            	return ret;
            }
        };

Log in to reply
 

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