两个栈实现队列
该问题是“有2个空栈\(s_1,s_2\)，出入栈运算都是\(O(1)\)代价的，要求用这2个栈实现一个队列，出入队运算都是\(O(1)\)摊还代价的”。用2个栈实现队列的思路很简单，把一组元素入栈\(s_1\)再出栈入栈到\(s_2\)就能把\(s_1\)的栈底变成\(s_2\)的栈顶，进而就能实现队头的出队。这里具体来看如何实现，首先对于入队运算，直接入栈\(s_1\)即可，对于出队运算，当\(s_2\)为空时把\(s_1\)的元素全部出栈并依次入栈\(s_2\)，最后弹出\(s_2\)的栈顶作为队头出队。当\(s_2\)非空，直接弹出\(s_2\)的栈顶作为队头出队即可。
上述过程中，每个元素的入队都是1次\(s_1\)的入栈，出队都是3次的\(s_1\)出栈、\(s_2\)入栈、\(s_2\)出栈操作。对于\(2n\)次队列操作，最好的情况是发生\(2n\)次入队操作，最坏的情况是发生\(n\)次入队、\(n\)次出队，对于最坏的情况，也仅意味着发生了\(4n\)次栈操作。所以此时的总代价是\(O(n)\)，每次操作的摊还代价是\(O(1)\)。下面是具体程序实现。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class Queue: def __init__(self): self.s1 = [] self.s2 = [] def put(self, x): self.s1.append(x) def get(self): if not self.s2: while self.s1: self.s2.append(self.s1.pop()) return self.s2.pop() |
队列的最大值(单调队列算法)
该问题是“实现1个队列，其支持求当前最大值的\(max\)运算，且出入队和\(max\)的摊还代价是\(O(1)\)”。该问题看起来与栈的最值问题类似，但栈每次\(pop\)后能回到上次\(push\)前，队列没有该性质，不易找到\(O(1)\)的\(max\)实现，但容易找到\(O(1)\)摊还代价的实现，比如用2个可\(O(1)\)代价求最大值的栈模拟队列。这里讨论另一种实现，各运算的实现步骤如下：
0) 初始化：创建空的普通队列\(q\)、空的双端队列\(dq\)，其中\(dq\)能查看左右队头；
1) \(put(x)\): \(x\)入队\(q\)。从右队头循环的出队\(dq\)若\(dq\)非空且右队头小于\(x\)。最后从\(dq\)右队头入队\(x\)；
2) \(get()\): 从\(q\)出队，出队元素计为\(x\)。此时\(dq\)也非空，若其最左队头等于\(x\)，则左队头出队1次。最后返回\(x\)；
3) \(max()\)：返回\(dq\)最左端元素；
想要分析上述步骤，必须先明确\(dq\)的意义，这里通过“命题+证明”讨论。
a) 设队列的\(dq = (x_0,x_1…x_n)\)有至少1个元素，任意\(x_i\)都在其\(q\)中且顺序相同。当\(dq\)只有1个元素时必须满足\(q\)中\(x_0\)前的元素都小于\(x_0\)。当\(dq\)多于1个元素时必须满足\(x_{i-1} \geq x_i\)，且\(q\)中\(x_{i-1},x_i\)间的元素都小于\(x_i\)，\(x_0\)前的元素都小于\(x_0\)；
b.1) 对于初始队列(\(q,dq\)为空)或满足(a)的队列，执行1次\(put(x)\)后满足(a)；
证明：初始队列显然可以。对于非初始队列，若\(x > x_0\)，\(x\)成为新\(dq\)队头，新\(dq\)只留有\(x\)这个元素，满足(a)。若\(x_n \geq x\)，\(x\)成为新\(dq\)队尾且不导致任何\(dq\)元素出队，满足(a)。若\(x_{i-1} \geq x > x_i\)，\(x\)会使\(dq\)中\(x_i\)和其后面的全部元素出队，并取代\(x_i\)位置。从\(q\)的角度看，\(x\)是其新队尾，而\(x_{i-1}\)到\(x\)间的元素全部小于\(x\)，因为\(x\)大于原来\(dq\)中的\(x_i,x_{i+1}…x_n\)，也满足(a)。
b.2) 对于满足(a)的队列，执行1次\(get\)后满足(a)或成为初始队列(\(q,dq\)为空)；
证明：设\(get\)的元素为\(x\)，若\(x\)不等于\(x_0\)，\(x\)只能是\(q\)中\(x_0\)前的元素，\(dq\)前后无变化，满足(a)。若\(x\)等于\(x_0\)，出队的\(x\)就是\(x_0\)本身，\(q,dq\)会同时出队\(x_0\)，新\(dq = (x_1,…x_n)\)，新\(q\)的\(x_1\)前的元素都是原来\(x_0,x_1\)间的元素，所以满足(a)。
根据(b)的2条结论可以知道，初始化队列后，其经过任意的\(get/put\)后不是初始队列(\(q,dq\)为空)就是满足(a)的。对于满足(a)的队列，其\(dq\)的左队头是\(dq\)中最大的，而\(dq\)中所有元素都是其在\(q\)“划分的区间”里的最大值，故\(dq\)的左队头是\(q\)中的最大值，进而\(max\)能正确返回最大值。更直观的可以看上面的图片，该图片是同一个队列中\(q,dq\)的对比。
在上述队列中，双端队列\(dq\)中的元素时刻被维护为从左到右单调递减的，这种队列称为单调队列，使用了单调队列的算法称为单调队列算法，是一类比较灵活的队列算法。下面讨论各操作的时间复杂度，设\(q,dq\)所有运算都是\(O(1)\)的，那么\(max,get\)也是\(O(1)\)的，对于初始队列，如果执行\(k\)次\(put\)或\(get/put\)，则至多有\(O(k)\)个元素出入队，而每个元素从入队到出队，至多从\(q,dq\)各出入队1次，故总代价是\(O(k)\)，摊还代价是\(O(1)\)。下面是程序实现。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | from collections import deque class MaxQueue: def __init__(self): self.q = deque() self.dq = deque() def put(self, x): self.q.append(x) while self.dq and self.dq[-1] < x: self.dq.pop() self.dq.append(x) def get(self): if not self.q: raise Exception('队列为空') x = self.q.popleft() if self.dq and self.dq[0] == x: self.dq.popleft() return x def max(self): if not self.q: raise Exception('队列为空') return self.dq[0] |
滑动窗口的最大值
该问题是“给定1个数值数组\(nums\)，1个固定的滑动窗口大小值\(k\)(窗口容纳的元素数)，其中\(k\)不大于\(nums\)的长度，这个滑动窗口会像上图一样从左到右，一次一个元素的滑动。要求从左到右的求出每个窗口的最大值，以数组形式返回”。很多滑动窗口型的问题都可以用队列算法解决，这个问题就可以用前面讨论过的最大值队列/单调队列直接解决。
这里分析下时间复杂度，这时的最大值队列是供另一个算法使用的。设\(nums\)大小为\(n\)，最大值队列共执行\(n\)次\(put\)和\(n-k\)次\(get\)，这时最大值队列的\(O(1)\)摊还代价就能看作\(O(1)\)实际代价，总代价是\(O(n)\)。具体程序如下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | from collections import deque class MaxQueue: def __init__(self): self.q = deque() self.dq = deque() def put(self, x): self.q.append(x) while self.dq and self.dq[-1] < x: self.dq.pop() self.dq.append(x) def get(self): if not self.q: raise Exception('队列为空') x = self.q.popleft() if self.dq and self.dq[0] == x: self.dq.popleft() return x def max(self): if not self.q: raise Exception('队列为空') return self.dq[0] def f(nums, k): mq = MaxQueue() result = [] for i in range(len(nums)): mq.put(nums[i]) if i >= k - 1: result.append(mq.max()) mq.get() return result |