Simple C++ O(n) Solution


  • 0
    J

    '''

    int candy(vector<int>& ratings) {
        int n = ratings.size();
        if (0 == n) return 0;
        vector<int> cnt(n, 1);
        for (int i = 1; i < n; i++)
        {
            if (ratings[i] > ratings[i - 1])
            {
                cnt[i] = max(cnt[i], cnt[i - 1] + 1);
            }
        }
        
        for (int i = n - 2; i >= 0; i--)
        {
            if (ratings[i] > ratings[i + 1])
            {
                cnt[i] = max(cnt[i], cnt[i + 1] + 1);
            }
        }
        
        int ret = 0;
        for (int x : cnt) ret += x;
        return ret;
    }
    

    '''


  • 0
    D

    What if the length is just 1. Hence, your algorithm will output 0. I think, we should set the values one in the first for loop if ratings[i] <= ratings[i+1];


  • 0
    J

    @datianshi21 I do NOT think so. See this line vector<int> cnt(n, 1), cnt is initialized by 1. So if length is 1, sum of cnt will be 1.


Log in to reply
 

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