C++ solution, 45ms, O(n) time and O(n) space, passed at the first attempt


  • 0
    Z
    class Solution {
    public:
        int candy(vector<int>& ratings) {
            int n=ratings.size();
            if(n<1) return 0;
            if(n==1) return 1;
            
            vector<int> flag;
            vector<int> pos;
            vector<int> results(n,1);
            int count=0;
            
            if(ratings[0]<ratings[1]){
                flag.push_back(1);
                pos.push_back(0);
                count++;
            }
            if(ratings[n-2]>ratings[n-1]){
                flag.push_back(1);
                pos.push_back(n-1);
                count++;
            }
            
            for(int i=1;i<n-1;i++){
                if(ratings[i]<ratings[i-1] && ratings[i]<ratings[i+1]){
                    flag.push_back(1);
                    pos.push_back(i);
                    count++;
                }
                if(ratings[i]<ratings[i-1] && ratings[i]==ratings[i+1]){
                    flag.push_back(2);
                    pos.push_back(i);
                    count++;
                }
                if(ratings[i]==ratings[i-1] && ratings[i]<ratings[i+1]){
                    flag.push_back(3);
                    pos.push_back(i);
                    count++;
                }
            }
            
            if(count>0){
                for(int j=0;j<count;j++){
                    int i=pos[j];
                    if(flag[j]==1){
                        while(ratings[i+1]>ratings[i] && results[i]+1>results[i+1]){
                            results[i+1]=results[i]+1;
                            i++;
                        }
                        
                        i=pos[j];
                        while(ratings[i-1]>ratings[i] && results[i]+1>results[i-1]){
                            results[i-1]=results[i]+1;
                            i--;
                        }
                    }
                    
                    if(flag[j]==2){
                        while(ratings[i-1]>ratings[i] && results[i]+1>results[i-1]){
                            results[i-1]=results[i]+1;
                            i--;
                        }
                    }
                
                    if(flag[j]==3){
                        while(ratings[i+1]>ratings[i] && results[i]+1>results[i+1]){
                            results[i+1]=results[i]+1;
                            i++;
                        }
                    }
                }
            }
            
            int sum=0;
            for(int i=0;i<n;i++)
            sum+=results[i];
            return sum;
        }
    };
    

    Although the code seems long, the idea is pretty simple. I just record three types of minimum points and do some calculations from the minimum points.


Log in to reply
 

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