135. Candy 发表于 2022-01-25 Greedy1234567891011121314151617181920212223242526272829class Solution { public int candy(int[] ratings) { int totalCount = 0; int[] counts = new int[ratings.length]; Arrays.fill(counts, 1); totalCount += counts.length; for (int i = 1; i < ratings.length; i++) { if (ratings[i] > ratings[i - 1]) { while (counts[i] <= counts[i - 1]) { counts[i]++; totalCount++; } } } for (int i = ratings.length - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { while (counts[i] <= counts[i + 1]) { counts[i]++; totalCount++; } } } return totalCount; }} Greedy123456789101112131415161718192021222324252627class Solution { public int candy(int[] ratings) { int[] left = new int[ratings.length]; Arrays.fill(left, 1); for (int i = 1; i < ratings.length; i++) { if (ratings[i] > ratings[i - 1]) { left[i] = left[i - 1] + 1; } } int count = left[left.length - 1]; int[] right = new int[ratings.length]; Arrays.fill(right, 1); for (int i = ratings.length - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { right[i] = right[i + 1] + 1; } count += Math.max(left[i], right[i]); // 注意该逻辑在 if 块外执行 } return count; }} Reference135. Candy