My c++ solution with o(1) space and o(n) time. I wonder where I can do better in some details.


  • 0
    H
    class Solution {
    public:
        int candy(vector<int>& ratings) {
            if (ratings.empty()) return 0;
            int cnt(1);
            bool up(false), down(false);
            int poten( (numeric_limits<int>::max)() );
            int NowHigh(1);
            for (int i = 1; i < ratings.size(); ++i) {
                if (ratings[i - 1] < ratings[i]) {
                    NowHigh = down? 1 : NowHigh;
                    cnt += (++NowHigh);
                    up = true;
                    down = false;
                }
                else if (ratings[i - 1] == ratings[i]) {
                    poten = (numeric_limits<int>::max)();
                    NowHigh = 1;
                    cnt += NowHigh;
                    up = false;
                }
                else if (ratings[i - 1] > ratings[i]) {
                    if(up) {
                        poten = NowHigh;
                        NowHigh = 1;
                        cnt += NowHigh;
                    }
                    else if (++NowHigh >= poten) {
                        cnt += (++NowHigh);
                        poten = (numeric_limits<int>::max)();
                    }
                    else
                        cnt += (NowHigh);
                    up = false;
                    down = true;
                }
            }
            return cnt;
        }
    };

Log in to reply
 

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