one pass constant space C++ solution.


  • 0
    A

    The idea is straightforward: if you draw a graph based on ratings, to satisfy minimum total number, the increasing line should always start with 1 candy; the decreasing line should always end with 1 candy. We can achieve that by following those rules:

    • In increasing line, i simply gets 1 more candy than i - 1;

    • In decreasing line, i simply gets 1 less candy than i -1. However, at the end of this decreasing trend, # of candy could be greater or smaller than 1; if this happens we just need to 'normalize' the # of candy from 'start of trend + 1' to end of trend.

    • If rating of i is the same as i - 1, it depends on previous trend.

    Code is a bit ugly but logic should be clear. Also run time seems to vary, got 29 ms first submission, then 43 and 36.

      class Solution {
      public:
    	  int candy(vector<int>& ratings) {
    		  if (ratings.empty())
    			  return 0;
    		  int ret(1);
    		  bool increase(true);
    		  int start(0)/*The begining of increasing/decreasing trend*/, lastCandy(1), lastRating(ratings[0]);
    		  for (int i = 1; i < ratings.size(); ++ i) {
    			  if (ratings[i] > lastRating) {
    				  if (increase) { // continue increasing
    					  ret += ++ lastCandy;
    				  } else {//start increasing
    					  if (lastCandy > 1) { // decrease # candies from start + 1 to i - 1
    						  ret -= (i - 1 - start) * (lastCandy - 1);
    					  } else { // increase # candies from start to i - 1
    						  ret += (i - start) * (1 - lastCandy);
    					  }
    					  lastCandy = 2; // i - 1 has 1 candy, i has 2
    					  ret += 2;
    					  start = i - 1;
    				  }
    				  lastRating = ratings[i];
    				  increase = true;
    			  } else if (ratings[i] < lastRating) {
    				  if (increase) { // start decreasing
    					  start = i - 1;
    				  } else
    					  ;
    				  ret += -- lastCandy;
    				  increase = false;
    				  lastRating = ratings[i];
    			  } else if (ratings[i] == lastRating) {
    				  if (increase) {
    					  ;
    				  } else {
    					  if (lastCandy > 1) { // decrease # candies from start + 1 to i - 1
    						  ret -= (i - 1 - start) * (lastCandy - 1);
    					  } else { // increase # candies from start to i - 1
    						  ret += (i - start) * (1 - lastCandy);
    					  }
    					  start = i;
    				  }
    				  ret ++;
    				  lastCandy = 1;
    			  }
    		  }
    		  if (!increase) { // normalize from start/(start + 1) to ratings[ratings.size() - 1]
    			  int i = ratings.size() - 1;
    			  if (lastCandy > 1) {
    				  ret -= (i - start) * (lastCandy - 1);
    			  } else {
    				  ret += (i - start + 1) * (1 - lastCandy);
    			  }
    		  }
    
    		  return ret;
    	  }
      };
    

Log in to reply
 

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