因为一个小朋友分得最少的情况与他旁边两个小朋友👬都有关🐶,因此需要从两边扫描。
细节有点折磨人,改了4次才pass,呵呵哒。
注意三个问题:
- 扫描的循环开始值,与终止条件,一般来说正着敦不容易出错,反着敦(如第二个循环)就容易把边界条件搞搞搞...错了
- 需要变更dp元素的情况是,ratings1 = dp2(注意此处等于号)
- 变更不能++dp[i],而需要在另一个元素的基础上+1
// // Created by jt on 2020/8/9. // class Solution { public: /** * * @param ratings int整型vector * @return int整型 */ int candy(vector &ratings) { // write code here // 设f(i)为第i个小朋友最少分到的糖果🍬数量,则f(i)与f(i-1)和f(i+1)有关 // 于是从两边分别扫描dp数组 int size = ratings.size(); vector dp(size, 1); for (int i = 1; i < size; ++i) { if (ratings[i] > ratings[i - 1] && dp[i] <= dp[i - 1]) dp[i] = dp[i-1] + 1; } for (int i = size - 2; i >= 0; --i) { if (ratings[i] > ratings[i + 1] && dp[i] <= dp[i + 1]) dp[i] = dp[i+1] + 1; } int sum = 0; for (int i = 0; i < size; ++i) { sum += dp[i]; } return sum; } };