My ac 36 ms C++ solution ( o(n) time and o(1) space)


  • 1
    Y
    class Solution {
    public:
        int candy(vector<int>& ratings) {
            if(ratings.empty())
                return 0;
            int result = 1;
            int down = 0, up = 1;
            bool newUp = true;
            for(int i = 1; i < ratings.size(); ++i) {
                if(ratings[i] > ratings[i - 1]) {
                    if(newUp) {
                        up = 2;
                        newUp = false;
                        result += up;
                        down = 0;
                    }
                    else {
                        ++up;
                        result += up;
                        down = 0;
                    }
                }
                else if(ratings[i] == ratings[i - 1]) {
                    up = 1;
                    down = 0;
                    result += 1;
                    newUp = true;
                }
                else{
                    ++down;
                    if(up == down)
                        ++down;
                    result += down;
                    newUp = true;
                }
            }
            return result;
        }
    };

Log in to reply
 

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