題目描述：
老師想給孩子們分發糖果，有 N 個孩子站成了一條直線，老師會根據每個孩子的表現，預先給他們評分。

你需要按照以下要求，幫助老師給這些孩子分發糖果：

每個孩子至少分配到 1 個糖果。
相鄰的孩子中，評分高的孩子必須獲得更多的糖果。

那么這樣下來，老師至少需要準備多少顆糖果呢？

示例 1:

輸入: [1,0,2]
輸出: 5
解釋: 你可以分別給這三個孩子分發 2、1、2 顆糖果。

示例 2:

輸入: [1,2,2]
輸出: 4
解釋: 你可以分別給這三個孩子分發 1、2、1 顆糖果。
第三個孩子只得到 1 顆糖果，這已滿足上述兩個條件

方法一：（暴力搜索）
兩個條件：

1. 每個孩子至少分配到 1 個糖果
2. 相鄰的孩子中，評分高的孩子必須獲得更多的糖果

即先給所有孩子分配一個糖果
滿足第二個條件的要求是：
a. ratings[i] > ratings[i-1] 且 candy[i] <= candy[i-1]，此時candy[i]的糖果數量需要在candy[i-1]的基礎上增加1(保證最終結果最小)
b. ratings[i] > ratings[i+1] 且 candy[i] <= candy[i+1], 此時candy[i]的糖果數量需要在candy[i+1]的基礎上增加1

實現如下:

int candy(vector<int>& ratings) {vector<int> candy(ratings.size(),1);bool flag = true;while (flag) {flag = false;for (int i = 0;i < ratings.size(); ++i) {if (i != ratings.size() - 1 && ratings[i] > ratings[i+1] &&candy[i] <= candy[i+1]) {candy[i] = candy[i+1] + 1;flag = true;}if (i > 0 && ratings[i] > ratings[i-1] && candy[i] <= candy[i-1]) {candy[i] = candy[i-1] + 1;flag = true;}}}int sum = 0;for (int i = 0;i < candy.size(); ++i) {sum += candy[i];}return sum;
}

以上方法最壞的時間復雜度：
O(n^2),對于每個元素，我們最多要遍歷n次

方法二：前后遍歷
取出條件2: 相鄰的孩子中，評分高的孩子必須獲得更多的糖果
即必須同時滿足：

1. a. ratings[i] > ratings[i-1] && candy[i] > candy[i-1]
2. b. ratings[i] > ratings[i+1] && candy[i] > candy[i+1]

針對第一種情況，我們可以從左向右遍歷一次即可滿足
針對第二種情況，我們可以從右向左遍歷一次即可滿足

以上過程整體為O(n)的時間復雜度，空間復雜度也為O(n)

實現如下:

int candy(vector<int>& ratings) {vector<int> candy(ratings.size(),1);//從左向右for (int i = 1; i < ratings.size(); ++i) {if (ratings[i] > ratings[i-1] && candy[i] <= candy[i-1]){candy[i] = candy[i-1] + 1;}}//從右向左for (int i = ratings.size() - 2; i >= 0; i--) {if (ratings[i] > ratings[i+1] && candy[i] <= candy[i+1]) {candy[i] = candy[i+1] + 1;}}int sum = 0;for (int i:candy) {sum += i;}return sum;
}

總結

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

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