学弟讲算法-数论-滑动窗口最值

题目

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位

实例

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3

输出: [3,3,5,5,6,7]

滑动窗口的位置最大值[1 3 -1] -3 5 3 6 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 3 -1 -3 5 [3 6 7]7

思路

此处使用双向队列(deque)这个数据结构

当前滑动窗口的最大值总是保存在队头，队列里数据从大到小排列

若遇到的值比队尾元素大,则将从队尾开始比该值小的元素出队,再将新值插入队尾中

若遇到的值比当队尾元素小,则直接插入到队尾

每次移动的时,判断队头元素(窗口最大值)是否在有效范围.若不在,将其从队列中删除

图示

num = [1,3,-1,-3,5,3,6,7] ,k = 3

原始数组队列res1 3 -1 -3 5 3 6 711 3 -1 -3 5 3 6 731 3 -1 -3 5 3 6 73,-131 3 -1 -3 5 3 6 73,-1,-33,31 3 -1 -3 5 3 6 753,3,51 3 -1 -3 5 3 6 75,33,3,5,51 3 -1 -3 5 3 6 763,3,5,5,61 3 -1 -3 5 3 6 773,3,5,5,6 ,7 原始数组队列res2 3 4 2 6 2 5 122 3 4 2 6 2 5 132 3 4 2 6 2 5 1442 3 4 2 6 2 5 14,24,42 3 4 2 6 2 5 164,4,62 3 4 2 6 2 5 16,24,4,6,62 3 4 2 6 2 5 16,54,4,6,6,62 3 4 2 6 2 5 15,14,4,6,6,6,5

最后一行: 队头6由于已经不在窗口范围内故删除

代码

//v:待处理元素;w:窗口大小 vector<int> maxSlideWindow(vector<int> v,int w) { vector<int> res; //q中储存的是v中元素的下标 deque<int> q; //处理前几个元素 for (int i = 0; i < w; i++) { while (!q.empty() && v[i] >= v[q.back()]) { q.pop_back(); } q.push_back(i); } for (int i = w; i < v.size(); i++) { //队头元素为当前窗口最大值 res.push_back(v[q.front()]); while //当前元素大于队尾元素时删除队尾元素 while (!q.empty() && v[i] >= v[q.back()]) { q.pop_back(); } //当队头元素(最大值)不在窗口范围内时删除队头元素 while (!q.empty() && q.front() <= i-w) { q.pop_front(); } q.push_back(i); } res.push_back(v[q.front()]); return res; }

补充

个人感觉难点在于删除队头元素(最大值)这一部分,下面在进行说明

对于第i个元素,若其是当前窗口的最大值,那么其有效的范围为[i-w+1,i]

元素 :2 3 4 2 6 2 5 1

下标 :0 1 2 3 4 5 6 7

从第三个元素4开始:

i = 2,v[2] = 4 ; i-w = -1 ; 有效范围:[0,2] ; q.front = 2 ;q = [2]i = 3,v[3] = 2 ; i-w = 0 ; 有效范围:[1,3] ; q.front = 2 ; q = [2,3]i = 4,v[4] = 6 ; i-w = 1 ; 有效范围:[2,4] ; q.front = 4 ; q = [4]i = 5,v[5] = 2 ; i-w = 2 ; 有效范围:[3,5] ; q.front = 4 ; q = [4,5]i = 6,v[6] = 5 ; i-w = 3 ; 有效范围:[4,6] ; q.front = 4 ; q = [4,6]i = 7,v[7] = 1 ; i-w = 4 ; 有效范围:[5,7] ; 原本队列q = [4,6,7],原本队头q.front = 4 <= i-w 不在有效范围内,故出队;新队列q = [6,7],新队头q.front = 6