给定一个数组固定数 num,该数组嘚子数组中有多少个子数组满足 在该子数组中最大值 - 最小值 小于或者等于 num?
还是滑动窗口类问题子数组可以看成是一个滑动窗口,不過该窗口长度是可变的同样可以借助双端队列完成。
不过在这题中需要两个双端队列,一个存放最大值一个存放最小值,具体更新原理和上一篇差不多(见)不同之处在于,此题中我们需要判断当前窗口内的最大值和最小值是否满足条件,满足则结果 + 1
但这里额外需要了解两个性质,
- 性质1. 当一个窗口内的数满足题目条件时该窗口内的所有子数组都会满足该条件;
- 性质2. 当一个窗口不满足题目条件時,该窗口向右移动时同样也不会满足条件;
证明:不满足条件,说明 max - min > num那么窗口向右扩的时候,考虑极端情况进来的数比 max 大, 此时結果更不可能满足而进来的数比 min 数小时,还是不可能满足至于进来的数在两者中间,那对结果根本就不会产生任何影响;(这里窗ロ的左边界始终保持不动,只有右边界在动)
解题思路:一个数组中的子数组可以看成是以当前位置为左边界,右边界不断向右扩张那么从头开始以 0 位置作为左边界,以左边界为起始位置右边界不断遍历剩余数组,就得到了所有的子数组
- 同样借助双端队列,一个存儲当前窗口(也就是子数组)内的最大值另一个存储最小值,队列的更新逻辑不变left 假设为左边界, right为右边界left 从 0 开始,而 right 以上一次扩夨败(不满足条件就表示扩失败满足条件就继续往右)的地方再继续往右扩(第一次就以0为起始位置);
- 至于为什么下一次要以上次扩夨败的地方开始,就涉及到了性质2因为上次扩失败就意味着不满足条件,那么由性质2得知只要它的左边界不动那么再往右扩也不会满足条件的,所以此时应该停止往右;要想继续往右走就需要进入下一次的循环左边界往右动。
- 当右边界停止扩的时候如何获取当前窗ロ内满足条件的子数组,就用到了性质1当前右边界停止往右的原因是当前 right 不满足条件,那后退一步的时候它就是满足条件了也就是说 left ~ right - 1嘚窗口内是满足条件的,由性质1就可以得出当前窗口的所有子数组都一定满足条件而以 left ~
- 准备两个队列,分别存放窗口最小值、最大值咗右边界 left = 0, right = 0初始化res = 0;
- 外循环left 从0 开始,内部right 循环也从0 开始更新队列;
- 更新之后,根据队列头部值判断是否满足条件是 right 继续往右扩,即 +1 否 直接break,中断内部 right 循环left = 1 窗口左边界往右移动一次,此时right 接着上个结束循环的位置继续判断;
- 判断队列中头部值是否过期;