一、題目大意
標簽: 貪心
https://leetcode.cn/problems/candy
n 個孩子站成一排，給你一個整數陣列 ratings 表示每個孩子的評分，
你需要按照以下要求，給這些孩子分發糖果：
每個孩子至少分配到 1 個糖果，
相鄰兩個孩子評分更高的孩子會獲得更多的糖果，
請你給每個孩子分發糖果，計算并回傳需要準備的 最少糖果數目 ，
示例 1：
輸入：ratings = [1,0,2]
輸出：5
解釋：你可以分別給第一個、第二個、第三個孩子分發 2、1、2 顆糖果，
示例 2：
輸入：ratings = [1,2,2]
輸出：4
解釋：你可以分別給第一個、第二個、第三個孩子分發 1、2、1 顆糖果，
第三個孩子只得到 1 顆糖果，這滿足題面中的兩個條件，
提示：
- n == ratings.length
- 1 <= n <= 2 * 104
- 0 <= ratings[i] <= 2 * 104
二、解題思路
這題我們只需要遍歷2次即可：把所有孩子的糖果初始化為1；先從左往右遍歷一遍，如果右邊孩子的評分比左邊的高，則右邊孩子的糖果數更新為左邊孩子的糖果數加1；再從右往左遍歷一遍，如果左邊孩子的評分比右邊的高，且左邊孩子當前的糖果數不大于右邊孩子的糖果數，則左邊孩子的糖果數更新為右邊孩子的糖果數加1，通過兩次遍歷，分配的糖果就可以滿足題目要求了，這里的貪心策略即為，在每次遍歷中，只考慮并更新相鄰一側的大小關系，
三、解題方法
3.1 Java實作
public class Solution {
public int candy(int[] ratings) {
int size = ratings.length;
if (size < 2) {
return size;
}
int[] num = new int[size];
Arrays.fill(num, 1);
for (int i = 1; i < size; i++) {
if (ratings[i] > ratings[i - 1]) {
num[i] = num[i - 1] + 1;
}
}
for (int i = size - 1; i > 0; i--) {
if (ratings[i] < ratings[i - 1]) {
num[i - 1] = Math.max(num[i - 1], num[i] + 1);
}
}
return Arrays.stream(num).sum();
}
}
四、總結小記
- 2022/7/13 倒數3天
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499070.html
標籤：其他
上一篇：如何正確的去計算顯示幕帶寬
下一篇：資料結構——光纖網路設計