Candy

原題鏈接Candy

n個孩子站成一排，分糖果。ratings[i]表示第i個孩子的等級，要求

• 每個孩子至少有一個糖果
• 高等級的孩子分得的糖果要高于相鄰的低等級的孩子分得的糖果

計算最少需要的糖果數

初始時每個孩子一個糖果可以滿足，相鄰孩子的糖果數量需要從兩方面考慮

首先，保證高等級的孩子分得的糖果比左邊相鄰的低等級的孩子分得的糖果多(由于求最少糖果數，所以只多一個即可)

然后，保證高等級的孩子分得的糖果比右邊相鄰的低等級的孩子分得的糖果多(同理也只多一個)

這樣就滿足比左右兩邊都多的情況

代碼如下

class Solution { public:int candy(vector<int>& ratings) {if(ratings.empty()) return 0;int n = ratings.size();/* 每個孩子至少分得一個糖果 */vector<int> candies(n, 1);/* 首先保證比左邊的低等級的孩子分得的糖果多1 */for(int i = 1; i < n; ++i)candies[i] = (ratings[i] > ratings[i - 1]) ? candies[i - 1] + 1 : candies[i];/* 然后保證比右邊的多，這里需要比較本身的糖果數和右邊糖果數+1的大小，選擇最大的 */for(int i = n - 2; i >= 0; --i)candies[i] = (ratings[i] > ratings[i + 1]) ? std::max(candies[i], candies[i + 1] + 1) : candies[i];/* 求和 */return std::accumulate(candies.begin(), candies.end(), 0);} };

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----分糖果问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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