浅谈单调队列:死海不是胡,单调队列不是行

By admin in 亚洲必赢活动砸金蛋 on 2018年10月24日

滑窗口最值问题

为一定一个长度为n的行列a1,a2,…ai,…,an,将一个长为k的滑动窗口起排最左端向右侧滑动。例如:初始时,窗口外的子序列为a1,a2,…,ak;当窗口往右侧滑动一号,此时窗口内的子序列变为a2,a3,…,ak+1。

我们若化解之题目是,给得长度为n的排及滑动窗口的大小k,求诸一个滑动窗口外的绝小值和极端老价值。

盖长为5的队列1,
3, 4, 5, 7滑动窗口k=3为例说明: 

第1只滑动窗口(1,
3, 4)的不过小价、最老价值分别吗1暨4;

第2单滑动窗口(3,
4, 5)的最好小价、最特别价值分别吗3同5;

第3单滑动窗口(4,
5, 7)的顶小值、最老价值分别吗4暨7。

局部行之有效之缓解思路

最为直接的思绪,可以枚举所有窗口(一共n-k+1个),扫描窗口内的各个一个因素求其极值。
整算法的日复杂度是O(n*k),当数规模比较生之时段(如n=10^6,k=10^4),该算法耗时比丰富。

任何一个爱想到的思路,将行建线段树(或者树状数组等等),该过程的光阴复杂度是O(n*logn),再经过n-k+1不良询问区间极值求每个窗口对承诺间隔的极端老(小)值。整体时间复杂度是O(n*logn)。

干燥队列:更美之笔触

同等种更加漂亮之缓解方式是乏味队列。那么,我们就来齐揭秘「单调队列」的黑面纱吧。

先是,第一个问题来了:干燥队列是排——吗?
字面上理解的话,单调队列肯定是行,没毛病。不然也啥不给单调栈呢。
只是,初中地理教员来言在先:死海不是西,是湖水,还是世界上低的湖。为毛不起个「死湖」的讳?!这个……就自行google/baidu吧。
扯远了,扯回来。
干燥队列,从严格意义及讲话还真的不是「队列」
好家伙是班呢?就是一中FIFO(First
In First
Out)的数据结构。所有设入队的要素,统一从队尾入队,再从队首出队。
但,「单调队列」却非是同等栽FIFO的数据结构。在干燥队列中,为了保障队列内元素的「单调」性,所有设入队的因素,统一从队尾入队,再由对首出队,否堪起对尾直接出队

单调队排的基本操作

放起有些神秘,先来看望单调队列(以递增队列为例)有哪基本的操作。

1.入队(push_back):对于需要入队的素,为掩护队列的递增性,如果队尾元素值大于待入队元素,则用对准尾元素从队列中弹奏有,重复这操作,直到队列为空或者队尾元素小于待入队元素。然后,再把需要入队元素添加到队末尾。

2.出队(pop):分被动的出队(为保护队列单调性,将元素从队尾弹出)和积极性的出队(和风土人情的序列一样,从拔首生出;但是出讲究,正是以此讲究让滑动窗口最值问题可以化解)。

用单调队列求解滑动窗口最值问题

下,一起来看望哪用单调(递增)队列来缓解滑动窗口的最为(小)值问题。

坐长为6底行1,
3, 4, 5, 7, 2和滑动窗口k=3为条例:

1)1入队,入队后行化[1];

2)3入队,3大于队尾元素1,入队后行化[1,
3];

3)4入队,4大于队尾元素3,入队后行化[1,
3, 4];

于4初步,已经形成了第1单滑动窗口,窗口外无限小价就是是班首元素1。

4)5入队,5大于队尾元素4,入队后行化[1,
3, 4, 5];

这会儿,队内发生4独因素,求第2独滑动窗口外最为小值的政策是:

取出队首元素,如果该因素不以滑窗口外,则以那个由队列中弹奏来,继续得到新的指向首元素,直到队首元素出现在窗口外;此时,队首元素即为窗口最小价。

当下也即是出队操作的「讲究」之处在。

在求得第2单滑动窗口的最好小值后,1出于无在滑行窗口外为弹来,队列化[3,
4, 5];

5)7入队,7大于队尾元素5,入队后行化[3,
4, 5, 7];

邀第3个滑动窗口的尽小价亚洲必赢活动砸金蛋,3由于不在窗口内出队,4每当窗口外,所以4乎第3独窗口的极其小值。队列化[4,
5, 7]。

6)2入队,为保安队列的单调性,依次弹出7,
5, 4,完成入队后,队列化[2]。

邀第4个滑动窗口最小值为2,队列保持不变换,依然为[2]。

岁月复杂度

略知一二单调队排的中心之一在于,所有被动的出队(在队尾被弹来)的要素,都无容许是当前所要窗口的最值。

由于序列中之每个元素就可能入队1赖,最多也说不定出队1潮,所以都摊下来,用单调队列求滑动窗口外无限小值的算法时间复杂度是O(n)。

类地,也堪运用单调递减队列来求得滑动窗口外之最好深价值问题。

单调队排的一个更实用的用,就是采取其滑动窗口最值优化动态规划问题的辰复杂度。

除此以外,关于此问题,你可以在这里小试牛刀。

c++源码实现

 1 #include <iostream>
 2 #include <vector>
 3 #include <deque>
 4 #include <cstdio>
 5 
 6 #define MAXN 10010
 7 
 8 class Data {
 9 public:
10     int val;
11     int idx;
12     Data() { val = idx =  0; }
13     Data(int x, int y):val(x), idx(y){}
14 };
15 
16 class OrderedQueue {
17 private:
18     Data que[MAXN]; //在部分机器上(如POJ的环境上,MAXN为10^6时,会出现Runtime Error,一种可行的方法是将其设置为全局变量(由于封装差,因此不提供这个版本的代码).
19     int front;
20     int back;
21     int window_size;
22     // true -> increasing(not strictly)
23     // false -> decreasing(not strictly)
24     bool order;
25 public:
26     OrderedQueue();
27     OrderedQueue(int window_size, bool order);
28     void push_back(Data d);
29     Data get_window_front(int pos);
30     void clear();
31     bool empty();
32 };
33 
34 OrderedQueue::OrderedQueue() {
35     window_size = 3;
36     order = true;
37     clear();
38 }
39 
40 OrderedQueue::OrderedQueue(int window_size, bool order) {
41     this->window_size = window_size;
42     this->order = order;
43     clear();
44 }
45 
46 void OrderedQueue::clear() {
47     front = back = 0;
48 }
49 
50 bool OrderedQueue::empty() {
51     return front == back;
52 }
53 
54 void OrderedQueue::push_back(Data d) {
55     while (front < back) {
56         Data tail = que[back - 1];
57         bool tag = order ? d.val > tail.val : d.val < tail.val;
58         if (tag) {
59             break;
60         } else {
61             back--;
62         }
63     }
64     que[back++] = d;
65 }
66 
67 Data OrderedQueue::get_window_front(int pos) {
68     while (front < back && que[front].idx < pos - window_size + 1) {
69         front++;
70     }
71     return que[front];
72 }
73 
74 
75 int main() {
76     int a[8] = {1, 3, -1, -3, 5, 3, 6, 7};
77     int wsize = 3;
78     OrderedQueue oq1 = OrderedQueue(wsize, true);
79     OrderedQueue oq2 = OrderedQueue(wsize, false);
80     for (int i = 0; i < 8; i++) {
81         oq1.push_back(Data(a[i], i));
82         oq2.push_back(Data(a[i], i));
83         if (i + 1 >= wsize) {
84             std::cout << "在区间[" << (i - wsize + 1) << "," << i << "]内的最小值为" <<  oq1.get_window_front(i).val << std::endl;
85             std::cout << "在区间[" << (i - wsize + 1) << "," << i << "]内的最大值为" <<  oq2.get_window_front(i).val << std::endl;
86         }
87     }
88     return 0;
89 }

 

  

style=”font-family: "courier new", courier; font-size: 14px”>本文为本创博文,如得转载请注明文章有处于及作者信息。

style=”font-family: "courier new", courier”> style=”background-color: initial”>微信扫二维码打赏,鼓励一下吧! 

亚洲必赢活动砸金蛋 1 style=”font-family: 仿宋”> style=”font-family: verdana, Arial, Helvetica, sans-serif”> 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2018 亚洲必赢app官方下载 版权所有