Readme

3578.Count-Partitions-With-Max-Min-Difference-at-Most-K

我们很容易想到令dp[i]表示以i为最后一段区间的结尾，可以得到的切割方案。此时我们需要考虑最后一段的起点位置j可以在哪里。

题目条件中“区间最大值与区间最小值的差”，很容易提示我们可以用deque来分别求区间的最大值和最小值。更具体地，当我们从nums[0]开始，不断加入元素，直至将nums[i]纳入区间时，我们可以得到此时区间的最大值a和最小值b：如果a-b>k，那么意味着区间太长，起点位置应该往右移动。这是因为区间越大，就越容易得到更大的a和更小的b，必然有更大的差值。区间越小，a-b的值就会越小，而且这是一个单调的过程。于是我们调整左端点j右移，每移动一次的过程中，我们查看一下nums[j]的退出是否会影响保存区间最大值和最小值的两个deque（因为我们知道当前最大值或最小值必然是deque的首元素）。直至我们将左端点移动到L的位置，意味着区间[L:i]恰好满足最大值与最小值之差小于k。

以上说明区间[L:i]是一个合法的切分，同理更小的区间[L+1:i]，[L+2:i]...都是满足条件的切分。既然确定了最后一个区间的切法，那么就有dp[i] = dp[L-1]+dp[L]+dp[L+1]...+dp[i-1] 显然，我们会用一个DP的前缀和数组presum来辅助，即dp[i] = presum[i-1]-presum[L-2].

记得得到上述的dp[i]之后，就可以同样更新presum[i]。

以1-index考虑的话，最终的结果就是dp[n]。