https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92007/Sliding-Window-algorithm-template-to-solve-all-the-Leetcode-substring-search-problem.
https://www.cnblogs.com/yuhan-TB/p/3765457.html
https://www.cnblogs.com/yuhan-TB/p/3765457.html
给你一个滑动窗口和一个数组,滑动窗口从数组第一个元素开始向后滑动,每滑动一下就计算当前窗口中对应的数组元素的最大值;
设置窗口长度为m,数组长度为n,有O(n*m)算法,用最大堆的O(n*lgm)算,利用已经比较过的元素之间关系的O(n)算法;
摘自博客 http://blog.csdn.net/sgbfblog/article/details/7967489
题目描述
给定一个数组A[],有一个大小为w的滑动窗口,该滑动窗口从最左边滑到最后边。在该窗口中你只能看到w个数字,每次只能移动一个位置。我们的目的是找到每个窗口w个数字中的最大值,并将这些最大值存储在数组B中。
例如数组A=[1 3 -1 -3 5 3 6 7], 窗口大小w为3。则窗口滑动过程如下所示:
Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 输入参数为数组A和w大小 输出为数组B,其中B[i]存储了A[i]到A[i+w-1]中w个数字的最大值。
二、最大堆解法
第1个方法思路简单,但是时间复杂度过高,因此需要改进。可以使用一个最大堆来保存w个数字,每次插入数字时只需要O(lgw)的时间,从堆中取最大值只需要O(1)的时间。随着窗口由左向右滑动,因此堆中有些数字会失效(因为它们不再包含在窗口中)。
- typedef pair<int, int> Pair;
- void maxSlidingWindow(int A[], int n, int w, int B[])
- {
- priority_queue<Pair> Q; //优先级队列保存窗口里面的值
- for (int i = 0; i < w; i++)
- Q.push(Pair(A[i], i)); //构建w个元素的最大堆
- for (int i = w; i < n; i++) {
- Pair p = Q.top();
- B[i-w] = p.first;
- while (p.second <= i-w) {
- Q.pop();
- p = Q.top();
- }
- Q.push(Pair(A[i], i));
- }
- B[n-w] = Q.top().first;
- }
如果数组本身有序,则里面的while循环不会执行,堆大小会增大到n。因为堆大小并不保持在w不变,因此该算法时间复杂度为O(nlgn)。
三、双向队列O(N)解法
最大堆解法在堆中保存有冗余的元素,比如原来堆中元素为[10 5 3],新的元素为11,则此时堆中会保存有[11 5 3]。其实此时我们可以清空整个队列,然后再将11加入到队列即可,即只在队列中保持[11]。使用双向队列可以满足要求,滑动窗口的最大值总是保存在队列首部,队列里面的数据总是从大到小排列。当遇到比当前滑动窗口最大值更大的值时,则将队列清空,并将新的最大值插入到队列中。如果遇到的值比当前最大值小,则直接插入到队列尾部。每次移动的时候需要判断当前的最大值是否在有效范围,如果不在,则需要将其从队列中删除。由于每个元素最多进队和出队各一次,因此该算法时间复杂度为O(N)。
- void maxSlidingWindow(int A[], int n, int w, int B[])
- {
- deque<int> Q;
- for (int i = 0; i < w; i++) {
- while (!Q.empty() && A[i] >= A[Q.back()])
- Q.pop_back();
- Q.push_back(i);
- }
- for (int i = w; i < n; i++) {
- B[i-w] = A[Q.front()];
- while (!Q.empty() && A[i] >= A[Q.back()])
- Q.pop_back();
- while (!Q.empty() && Q.front() <= i-w)
- Q.pop_front();
- Q.push_back(i);
- }
- B[n-w] = A[Q.front()];
- }