Share a AC recursive solution. Hope it is helpful.


  • 0
    W

    I think this O(n) recursive solution is easy to understand.

    class Solution {
    public:
        int candyHelper(vector<int>& ratings, vector<int>& nums, int idx, int N){
             if( nums[idx] != 0 )
                 return nums[idx];
             int low = 0; int high = 0;
             if( idx == 0 ) low = high = idx + 1;
             else if( idx == N-1) low = high = idx - 1;
             else{
                 if( ratings[idx-1] <= ratings[idx+1] ){
                     low = idx - 1; high = idx +1;}
                 else{
                     low = idx + 1; high = idx-1;
                 }
             }
             if( ratings[idx] <= ratings[low])
                 nums[idx] = 1;
             else if ( ratings[idx] <= ratings[high])
                 nums[idx] = candyHelper(ratings, nums, low, N) + 1;
             else
                 nums[idx] = max(candyHelper(ratings, nums, low, N),candyHelper(ratings, nums, high, N)) + 1;
             return nums[idx];
        }
    
        int candy(vector<int> &ratings) {
            int N = ratings.size();
            if( N == 0) return 0;
            if( N == 1) return 1;
            vector<int> nums(N,0);
            int sum = 0;
            for( int i = 0; i < N; i++){
                sum += candyHelper(ratings, nums, i, N);
            }
            return sum;
        }

Log in to reply
 

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