前言#
今天这道题是困难的！
题目#
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1个糖果。 - 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例 1：
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。示例 2：
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。提示：
n == ratings.length1 <= n <= 2 * 1040 <= ratings[i] <= 2 * 104
分析#
看到最多最少，那么第一想法自然是动态规划。
然后第二想到的应该是一维数组应该可以做到O(n)的时间复杂度。
这道题还有个很明显的点，就是dp[i]和dp[i - 1]以及dp[i + 1]有关系。
很明显它仨存在dp[i] = max(dp[i - 1], dp[i + 1]) + 1的关系。
诶，不仅和i - 1有关，还得和i + 1有关，也就是和未来的元素有关。
还记得之前说过的：如果当前计算涉及到之后的元素，不妨考虑下预处理么？
也就是先走一遍，然后再走一遍就能得出结果，O(2n)也是O(n)。
那么对于这道题，我们可以先从左到右过一遍，得出dp[i]和dp[i - 1]的关系，很明显，当他俩满足ratings[i] > ratings[i - 1]的时候存在dp[i] = dp[i - 1] + 1，否则按最小的计算。
然后第二遍我们从右往左过一遍，此时dp我们已经有了，所以我们可以使用dp[i] = max(dp[i - 1], dp[i + 1]) + 1的关系，这样得出来的结果就是最终的结果。
ok，那么这道题也就豁然开朗了。
解#
pub fn candy(ratings: Vec<i32>) -> i32 {
let len = ratings.len();
match len {
0 => 0,
1 => 1,
_ => {
let mut dp = vec![1; len];
for i in 0..len - 1 {
let left = ratings[i];
let right = ratings[i + 1];
if left > right {
// 先一个一个的加
dp[i] = dp[i] + 1;
} else if left < right {
dp[i + 1] = dp[i] + 1;
}
}
dbg!(&dp);
// 这样拿到一个往右走完了的dp，接下来我们再往回走即可。
for i in (1..=len - 2).rev() {
let left = ratings[i + 1];
let right = ratings[i - 1];
let target = ratings[i];
// 因为我们是倒过来的，所以原本dp[i - 1]在这里是dp[i + 1]
// 递增的场景，这个时候dp[i] = dp[i + 1] + 1;
// 还有特殊情况需要单独处理，因为dp[i]和dp[i - 1]或者dp[i + 1]可能相等，这种情况不需要加1
if target <= left && target <= right {
// 因为相等也不算是高，所以这里需要重置为1
dp[i] = 1;
} else if target >= left && target >= right {
if dp[i + 1] > dp[i - 1] && left == target {
dp[i] = dp[i - 1] + 1;
} else if dp[i + 1] < dp[i - 1] && right == target {
dp[i] = dp[i + 1] + 1;
} else {
dp[i] = dp[i + 1].max(dp[i - 1]) + 1;
}
} else if target >= left && target < right {
dp[i] = dp[i + 1] + 1;
} else if target < left && target >= right {
dp[i] = dp[i + 1].min(dp[i - 1]) + 1;
}
}
// 从右往左没办法处理第一个元素，所以这里补充下
if ratings[0] > ratings[1] {
dp[0] = dp[1] + 1;
} else {
dp[0] = 1;
}
dbg!(&dp);
dp.iter().sum()
}
}
}这里我第一次是dp[i]和dp[i + 1]，没差，都一样的。
第一次我们拿到一个基本处理过的dp，然后第二次开始微调。
不过这里要考虑的场景还是比较多的，因为需要比较三个数。
测试用例#
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_candy() {
assert_eq!(candy([1, 0, 2].to_vec()), 5);
// [1, 2, 1]
assert_eq!(candy([1, 2, 2].to_vec()), 4);
// [1, 2, 1, 2, 1]
// [1, 3, 1, 2, 1]
assert_eq!(candy([1, 3, 2, 2, 1].to_vec()), 7);
// [1,2,3,1,3,2,1]
// [1, 2, 3, 1, 2, 2, 1] // 这是从左到右，只处理dp[i]和dp[i - 1]
// [1, 2, 3, 1, 3, 2, 1]
assert_eq!(candy([1, 2, 87, 87, 87, 2, 1].to_vec()), 13);
// [1, 2, 3, 3, 2, 1]
assert_eq!(candy([29, 51, 87, 87, 72, 12].to_vec()), 12);
// [1, 2, 3, 4, 1]
// [1, 2, 3, 3, 1]
assert_eq!(candy([1,3,4,5,2].to_vec()), 11);
// [3, 2, 1, 1, 2, 1, 1]
// [2, 2, 1, 1, 2, 1, 1]
assert_eq!(candy([3,2,1,1,4,3,3].to_vec()), 11);
// [1, 2, 3, 2, 1]
// [1, 2, 3, 3, 1]
assert_eq!(candy([1,2,4,4,3].to_vec()), 9);
}
}总结#
这道题的重点是预处理，因为我们需要知道dp[i + 1]，所以我们先行处理一波，这样就有一个基本的dp[i + 1]。