双端队列的应用题解

2024-03-18 10:48

文章标签 队列双端应用题

本文主要是介绍双端队列的应用题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 生成窗口最大值数组
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：

[4 3 5] 4 3 3 6 7 窗口中最大值为5
4 [3 5 4] 3 3 6 7 窗口中最大值为5
4 3 [5 4 3] 3 6 7 窗口中最大值为5
4 3 5 [4 3 3] 6 7 窗口中最大值为4
4 3 5 4 [3 3 6] 7 窗口中最大值为6
4 3 5 4 3 [3 6 7] 窗口中最大值为7

如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。请实现一个函数，给定一个数组arr，窗口大小w。返回一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的最大值。以本题为例，结果应该返回[5,5,5,4,6,7]。

#include <iostream>
#include <vector>
#include<string>
#include<algorithm>
#include<deque>
using namespace std;
vector<int> findWindowMax(vector<int> &nums,int w) {int len = nums.size();if (len <= 0 || w > len) return vector<int>();deque<int>deq;vector<int>res(len-w+1);int index = 0;for (int i = 0; i < len; i++) {while (!deq.empty() && nums[deq.back()] <= nums[i])deq.pop_back();     //弹出最后一个元素deq.push_back(i);if (i - deq.front() == w) deq.pop_front(); //判断元素是否过期，双端队列中最多有w个元素，超过即弹出if (i >= w - 1)      //w=3时,i=2时即第一个窗口的最大值要记录res[index++] = nums[deq.front()];}return res;
}
int main() {vector<int> v = { 4,3,5,4,3,3,6,7 };vector<int> res = findWindowMax(v, 3);for (auto c : res)cout << c << endl;
}

最大值减去最小值小于或等于num的子数组数量
给定数组arr和整数num，返回有多少个子数组满足如下情况:
max(arr[i..j]) - min(arr[i..j]) <=num
max(arr[i..j])表示子数组arr[i..j]中的最大值，min(arr[i..j])表示子数组arr[i..j]中的最小值。如果数组长度为 N，请实现时间复杂度为 O(N)的解法。
分析：求出arr[i,j]中最大值减去最小值小于等于num的子数组的数目
有两个性质
(1)若arr[i,j]不满足要求，那么arr[i,j]的扩展数组也绝对不会满足要求
(2)若arr[i,j]满足要求，那么arr[i,j]的子数组也绝对会满足要求
deq_max保存子数组arr[i,j]的最大值并且是递减的
deq_min保存子数组arr[i,j]的最小值并且是递增的
时间复杂度：虽然有多重循环，但是i和j都没有退回，每次j停止，i最多向前移动到j位置，故为O(2*N)
内部的元素入队列和出队列也只是n次，故时间复杂度仍然为O(N).

int findMax(vector<int> &nums, int num) {int len = nums.size();if (len == 0||len==1) return 0;deque<int> deq_max, deq_min;  //deq_max 依次减小，头最大，而deq_min相反int j = 0;int res = 0; // 保存子数组的个数  for (int i = 0; i < len; i++) {for (; j < len; j++) {while (!deq_max.empty() && nums[deq_max.back()] <= nums[j])deq_max.pop_back();deq_max.push_back(j);while (!deq_min.empty() && nums[deq_min.back()] >= nums[j])deq_min.pop_back();deq_min.push_back(j);if (nums[deq_max.front()] - nums[deq_min.front()]> num) break;}if (deq_max.front() == i) deq_max.pop_front();  //这里，如果最大值在i处，让其弹出，因为我们要让i++if (deq_min.front() == i) deq_min.pop_front();  //同理res += j - i;   // j-i就是子数组的数量  }return res;
}
int main() {vector<int> v = { 4,3,5,4,3,3,6,7 };cout<< findMax(v, 1);
}