首页 > 代码库 > Candy [leetcode] O(n)时间复杂度,O(1)空间复杂度的方法

Candy [leetcode] O(n)时间复杂度,O(1)空间复杂度的方法

对于ratings[i+1],和ratings[i]的关系有以下几种:

1. 相等。相等时ratings[i+1]对应的糖果数为1

2.ratings[i + 1] > ratings[i]。在这种情况下,要寻找以ratings[i]开始的递增序列。

3.ratings[i + 1] < ratings[i]。在这种情况下,要寻找以ratings[i]开始的递减序列。

对于任意一个递增序列 [2 3 4 5 6] 对应的糖果数为 [1 2 3 4 X]

对于任意一个递减序列[6 5 4 3 2]对应的糖果数为[X 4 3 2 1]

X为递增和递减序列交际处的元素对应糖果数。应该是递增序列长度和递减序列长度中较大的值

代码如下:

    int candy(vector<int> &ratings) {
        if (ratings.size() == 0) return 0;
        int sum = 0;
        int candyNum = 1;
        for (int i = 0; i < ratings.size() - 1;)
        {
            if (ratings[i] == ratings[i + 1]) 
            {   
               //if is the same rating, reset candy num. ie: 1 3 3, for the 2nd 3, candy num is 1
                sum += candyNum;//add current candy num
                i++;
                candyNum = 1;//set next candy num to 1
            }
            else if (ratings[i] < ratings[i + 1])
            {   
                // find ascending sequence, until i is the end of sequence. ie: 1 2 3 1, ratings[i] is 3
                for (;i < ratings.size() - 1 && ratings[i] < ratings[i + 1]; i++) sum += (candyNum++);
            }
            else if (ratings[i] > ratings[i + 1])
            {  
                // find descending sequence, until i is the end of sequence. ie: 3 2 1 3, rating[i] is 1
                int decCount = 1;
                for (; i < ratings.size() - 1 && ratings[i] > ratings[i + 1]; i++) sum += (decCount++);
                sum += max(candyNum, decCount);//add first element of the sequence
                //remove last element of the sequence, as i is the end of sequence, and i's candy num shouldn't be calculated into sum
                sum --;
                candyNum = 1;
            }
        }
        sum += candyNum;
        return sum; 
    }


Candy [leetcode] O(n)时间复杂度,O(1)空间复杂度的方法