Leetcode | Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

首先关于题意，higher rating get more candies， 但是如果是equal呢，可以比它的邻居多，也可以比它的邻居少。 也就是说，假设 rating=[2,4,4,4,2]，那么结果可以是[1,2,1,2,1].

分析一下知道，需要对于连续上升和下降趋势计数。对于平行的趋势，中间的都可以设为1。初始状态可以看作平行趋势。对于平行趋势到上升（或下降）趋势时的变化，其实就和初始一样。

平行状态：每个children可以只给一颗糖。比如rating=[4,4,2]，那么结果就是[1,1,2]；

下降状态：下降状态需要设置上升趋势的初始计数为2（这是因为下降实际是以1,2,...,n再翻过来去计数的，翻过来之后最后一个是1,所以上升的初始应该是2），这样才能正确地从下降到上升的转换。比如rating=[3,1,4]，计数是[1,2,2]，最终结果是[2,1,2]；

上升状态：上升状态需要设置下降趋势的初始计数为1。为了确保下降的计数翻转过来之后，下降的第一个点会比上升的最后一个点的糖数少。我们必须在计算下降趋势的时候，如果大于或等于之前上升趋势的最大趋势，我们就要在最终的计数加1。比如rating=[1,3,6,5,4,3,2,1]，计数是[1,2,3,1,2,3,4,5]，下降趋势部分翻转过来就是[1,2,3,5,4,3,2,1]，当下降计数>=3时就可累加1，这一部分1可以看作是累加到上升趋势的最后一个数上，也就是[1,2,6,5,4,3,2,1]。

初始状态：对于N>1，第一个可以直接先计着，从2开始，将第i元素与第i-1元素比较判断处于哪个状态。初始状态和平行状态一样。根据上面的分析，上升趋势初始值为2，下升趋势初始值为1. 前一个上升趋势的最大值为1. 

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        if (n <= 1) {
            return n;
        }
        
        int sum = 1, increasing = 2, decreasing = 1, maxIncreasing = 1;
        
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                maxIncreasing = increasing;
                sum += increasing++;
                decreasing = 1;
            } else if (ratings[i] == ratings[i - 1]) {
                increasing = 2;
                decreasing = 1;
                maxIncreasing = 1;
                sum++;
            } else {
                sum += decreasing++;
                if (decreasing > maxIncreasing) {
                    sum++;
                }
                increasing = 2;
            }
        }
        
        return sum;
    }
};

时间复杂度O(n)，空间复杂度O(1)。

第二次刷，照着思路写，卡在第16行了。应该只要是上升趋势就要更新pre. pre就是上升趋势的最大值。pre的初始值就应该很大。 120ms

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        if (n <= 1) return n;
        
        int sum = 1, pre = ratings.size() + 1, candy = 1, state = -1;
        
        for (int i = 1; i < ratings.size(); ++i) {
            if (ratings[i - 1] < ratings[i]) {
                if (state == -1 || state == 1) {
                    candy++;
                } else {
                    candy = 2;
                }
                pre = candy;
                state = 1;
            } else if (ratings[i - 1] > ratings[i]) {
                if (state == -1 || state == 0) {
                    candy++;
                    if (candy >= pre) sum++;
                } else {
                    candy = 1;
                }
                state = 0;
            } else {
                candy = 1;
                state = -1;
                pre = ratings.size() + 1;
            }
            sum += candy;
        }

        return sum;
    }
};

 Method II

网上有另一种解决思路，需要扫两遍，一遍是从左到右扫，一遍是从右到左扫，这样得到两个最小糖数组，最后对这两个数据每个位置求一下最大值就可以了。这样的时间复杂度仍是O(n)，空间复杂度也是O(n)。思想和Trapping Rain Water类似。

和z神讨论了一下，z神给出了一个不需要O(n)空间的做法，想想也是。

有两个指针，左指针指向的是当前位置左边连续递减的边界位置；右指针指向的是当前位置右边连续递减的边界位置；

每个位置的糖数由max(cur - left, right - cur) + 1决定；

但是要额外注意一下相等的情况。如果ratings[i] == ratings[i-1]的话，那么left=cur; 如果ratings[i]==ratings[i+1]的话，那么right=cur；

左指针的更新在O(n)可以做到，右指针的更新最怀情况是O(2n)。

对于右边的递减序列，右指针的更新只在right<=cur的时候才有必要更新。如果right>cur，证明当前还在递减序列当中，所以right不变。(Line14)

class Solution {
public:
    int candy(vector<int> &ratings) {
        int n = ratings.size();
        if (n <= 1) return n;
        ratings.push_back(ratings.back() + 1);
        int sum = 0, l = 0, r = 0, candy1 = 0;
        for (int i = 0; i < n; ++i) {
            if (i == 0 || ratings[i] <= ratings[i - 1]) {
                l = i;
            } 
            if (ratings[i] <= ratings[i + 1]) {
                r = i;
            } else if (r <= i) {
                r = i;
                for (int j = i + 1; ratings[j] < ratings[j - 1]; ++j) r++;
            }
            sum += max(r - i, i - l) + 1;
        }
        ratings.pop_back();
        return sum;
    }
};

 136ms

如果没有Line 14，就是1780ms。

第三次刷，最容易想出来的还是正反向扫一遍的做法。算是一次过吧。--i老是容易写成++i。

class Solution {
public:
    int candy(vector<int> &ratings) {
        if (ratings.empty()) return 0;
        int n = ratings.size();
        vector<int> dp(n, 0);
        for (int i = 1; i < n; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        
        int min = 0, right = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (i != n - 1 && ratings[i] > ratings[i + 1]) {
                right++;
            } else {
                right = 0;
            }
            min += max(dp[i], right) + 1;
        }
        return min;
    }
};