C#, O(n) one-pass, O(1) space, beats 90+%


  • 0
    H
    public class Solution {
    public int Candy(int[] ratings) {
        var candy = 0;
        var prevLo = 0;
        var prevHi = 0;
        var prevHiVal = Int32.MaxValue;
        for(int i = 0; i < ratings.Length; i++)
        {
            if(i == 0 || ratings[i] > ratings[i-1])
            {
                prevHi = i;
                prevHiVal = i - prevLo + 1;
                candy += prevHiVal;
            }
            else if (ratings[i] < ratings[i-1])
            {
                prevLo = i;
                if(i - prevHi < prevHiVal)
                {
                    candy += (i - prevHi);
                }
                else
                {
                    candy += (i - prevHi + 1);
                }
            }
            else
            {
                prevLo = i;
                prevHi = i;
                prevHiVal = 1;
                candy += 1;
            }
        }
        return candy;
    }
    

    }


Log in to reply
 

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