Leetcode: Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

下面这种做法类似于冒泡排序，复杂度有点高，但是Accepted

int candy(vector<int> &ratings) {  
        // Note: The Solution object is instantiated only once.  
        int sz = ratings.size();  
        if(sz < 2) return 1;  
        vector<int> candy(sz, 1);  
        bool changed = true;  
        while(changed)  
        {  
            changed = false;  
            for(int i = 0; i < sz; i++)  
            {  
                if(i-1>=0 && ratings[i] > ratings[i-1] && candy[i] <= candy[i-1])  
                {  
                    changed = true;  
                    candy[i] = max(candy[i-1]+1,candy[i]);  
                }  
                if(i+1<sz && ratings[i] > ratings[i+1] && candy[i] <= candy[i+1])  
                {  
                    changed = true;  
                    candy[i] = max(candy[i+1]+1,candy[i]);  
                }  
            }  
        }  
        int res = 0;  
        for(int i = 0; i< sz; i++)  
            res += candy[i];  
        return res;  
    }

补充：软件开发 , C++ ,