題目鏈接

兩次遍歷，首先初始化所有的糖果為1，然后從左向右遍歷，滿足$ratings[i]>ratings[i?1],num[i]=num[i?1]+1$。同理從右向左遍歷。
最終的結果是，要么是從1連續遞增，要么是從n連續遞減到1。

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

總結

以上是生活随笔為你收集整理的贪心 - 分发糖果的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。