LC

题目

算法1——记忆化搜索

这其实是滑雪问题的一维版本，但是略有不同，滑雪问题求的是一个点能走的最大距离，此题求的是所有点能走的最大距离之和。

假设答案为$ans$，不妨设第$i$个小朋友最终分得$f[i]$颗糖，则有：

$$ans = \sum_i f[i]$$

我们需要确定$ans$的下界。

把小朋友们的得分数组看成一堆柱子，柱子的高度就是得分。考察第$i$根柱子，如果它比左右的柱子高，则从从它可以往左、右下降（想象是下楼梯），直到出现上升的柱子停止。假设最远能往下走$S[i]$步。

可以看出$f[i] \ge S[i]$。

我们相求$ans$的下界，只需要看$f[i]$能否取到$S[i]$即可。当$f[i] = S[i]$时，不违反题目的条件，因此可以取到。因此我们得到，$ans$的最小值就是$\sum_i S[i]$。

那么如何求$S[i]$呢？需要利用记忆化搜索的方式，这里就和滑雪是一样的了。

代码

class Solution {
public:
    vector<int> c;
    vector<int> f;

    int candy(vector<int>& ratings) {
        c = ratings;
        f.resize(c.size(), -1);
        int res = 0;
        for(int i = 0; i < c.size(); i++) res += dp(i);
        return res;
    }

    int dp(int x) {
        if(f[x] != -1) return f[x];
        f[x] = 1;
        if(x && c[x - 1] < c[x]) f[x] = dp(x - 1) + 1;
        if(x < c.size() - 1 && c[x] > c[x + 1]) f[x] = max(f[x], dp(x + 1) + 1);
        return f[x];
    }
};

算法2——左右扫描

此题也可以分别从左往右和从右往左贪心，把规则拆分成2个子规则：

  1. 当前点如果得分高于相邻左边的点，那么应分得更多的糖果；
  2. 当前点如果得分高于相邻右边的点，那么应分得更多的糖果；

从而算出需要给第$i$个小朋友左边/右边多少颗糖。最后左右求一个max即可（取max是因为我们要同时满足1，2规则）

代码

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> g(n, 1);

        for(int i = 1; i < n; i++) {
            if(ratings[i] > ratings[i - 1])
                g[i] = g[i - 1] + 1;
        }

        int res = 0, r = 1;
        for(int i = n - 1; i >= 0; i--) {
            if(i < n - 1 && ratings[i] > ratings[i + 1]) {
                r++;
            } else {
                r = 1;
            }
            res += max(g[i], r);
        }
        return res;
    }
};