Share an ugly but correct O(1) space O(n) time (1 pass) solution.


  • 0
    F

    Not sure if it can be improved to look elegant.

    class Solution {
    public:
        int candy(vector<int>& ratings) {
            if (ratings.empty()) return 0;
            int gd_cnt = 0, cur = 1, sum = 1; // gd_cnt: going down count -- how many steps of going down so far. cur: candy for current kid. Not accurate.
            for (int i = 1; i < ratings.size(); ++i)
            {
                if (ratings[i-1] <= ratings[i])
                {
                    if (gd_cnt > 0)
                    {
                        //this part adjusts the sum by comparing how deep it went. If it went below 1, we will increase sum. Or we will decrease sum.
                       if (cur > 1)
                        {
                            sum += gd_cnt * (1 - cur);
                        }else{
                            sum += (gd_cnt + 1) * (1 - cur);
                        }
    
                        cur = 2;
                        gd_cnt = 0;
                    }else{
                        cur++; //r(i-1) < r(i), increase candy
                    }
                    if (ratings[i - 1] == ratings[i]) //r(i-1) = r(i), reset candy
                    {
                        cur = 1;
                    }
                }else {
                    cur--;  //r(i-1) > r(i), decrease candy
                    gd_cnt ++;
    
                }
                sum += cur;
            }
            if (gd_cnt > 0)
            {
                if (cur > 1)
                {
                    sum += gd_cnt * (1 - cur);
                }else{
                    sum += (gd_cnt + 1) * (1 - cur);
                }
    
            }
            return sum;
        }
    };

Log in to reply
 

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