前言

今天这道题是困难的！

题目

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

示例 1：

示例 2：

提示：

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= 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，那么这道题也就豁然开朗了。

解

这里我第一次是dp[i]和dp[i + 1]，没差，都一样的。

第一次我们拿到一个基本处理过的dp，然后第二次开始微调。

不过这里要考虑的场景还是比较多的，因为需要比较三个数。

测试用例

总结

这道题的重点是预处理，因为我们需要知道dp[i + 1]，所以我们先行处理一波，这样就有一个基本的dp[i + 1]。