【面试题 - 最大值减去最小值小于或等于 num 的子数组数量】滑动窗口

题干：

解题报告：

我们用两个指针（i，j）分别代表窗口的左边界和右边界，窗口也就是子数组；
用两个双端队列分别维护这个窗口的最大值和最小值；
当窗口扩大时，即j向右扩展时，窗口内的最大值只会越来越大，而最小值只会越来越小（否则就会等于原来的max和min了），此时，如果max-min>num，则j不应该向右扩展了，因为max-min的范围只会越来越大；
这时，应该让窗口缩小，即i向右扩展，这样max可能会减小，min可能会增大（因为原来的max和min可能会失效，即不在窗口内），这样max-min才会有<=num的可能；

另一个题解：

1）最简单的方法，暴力搜索，如何得到全部满足条件的子数组，
          left = 0， res=0；
          1：我们left不变 right++直到right=arr.length结束，每次right++我们都得到left~right的最大值，最小值 符合条件res++；
          2：然后left++ 重复第一步。

2）首先我们不用遍历n*n次，
          当满足条件right++  不满足时left++  这样时间复杂度为n*2；
          原因：当最大值-最小值>k时 我们right++ 如果arr[right]>最大值 或者arr[right]<最小值 差值都是增大的因此在移动right没有意义。
           left++，将子数组缩小，
           如果移除的数字是最大值，那么次大值-最小值 差值缩小；
           如果移除的数字是最小值，那么最大值-次小值 差值缩小；
           如果移除的是其他数字 差值不变；
           这样的时间复杂度变为n*2。

3）以上两种方法在left和right移动的过程中都要不断进行min和max的判断，提高了时间复杂度。

在遍历过程中不断更新qmin和qmax。

其中补充两个关键点：

1）如果nums[i..j]满足条件, nums[k..j]  (i<= k <= j)，都满足条件；

2）如果nums[i..j]不满足条件，所有包含 nums[i..j] 的数组都不满足条件；

AC代码：

class Solution { public:int getNum(vector<int> nums, int target){if(nums.empty())return 0;deque<int> qmin; //保存窗口内的最小值，递增 front保存最小的元素位置deque<int> qmax; //保存窗口内的最大值，递减 front保存最大的元素位置int i = 0, j = 0; //nums[i..j]表示数组的范围int res = 0; //表示满足条件的子数组数量//依次找到以nums[0],nums[1]...nums[N - 1]作为第一元素的子数组中满足条件的数量有多少个，累加while(i < nums.size()){while(j < nums.size()) // j向右拓展，直到不满足条件{while(!qmin.empty() && nums[qmin.back()] >= nums[j]) // 更新qmin中最小值的indexqmin.pop_back();qmin.push_back(j);while(!qmax.empty() && nums[qmax.back()] <= nums[j]) // 更新qmax中最大值的indexqmax.pop_back();qmax.push_back(j);if(nums[qmax.front()] - nums[qmin.front()] > target) //如果出现不满足条件的，那么包含以nums[i]起始的窗口的所有子数组都不满足条件break;j++;}if(qmin.front() == i) // 如果窗口为 0 ，直接弹出qmin.pop_front();if(qmax.front() == i) // 如果窗口为 0 ，直接弹出qmax.pop_front();res += j - i; //如果nums[i..j]满足条件，则其子数组都满足条件， 一共 (j - i)个子数组i++; //继续寻找以nums[i]为起始点的子数组}return res;}};

 

总结

以上是生活随笔为你收集整理的【面试题 - 最大值减去最小值小于或等于 num 的子数组数量】滑动窗口的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。