单调优先队列(monotone-priority-queue)

algorithm

(Banner图片来自一喜欢摄影的同学：心碎乌托邦)

综述

基本概念

使用双端队列(deque)实现单调的优先队列，保证队列中的元素始终是单调的。

示例

下面构造一个单调递增的优先队列，每次从队首插入元素，如果队首的元素小于该元素， 则弹出队首的元素，直至队首元素不小于插入元素。 

1
[2,3,5,1,4]
//依次插入单调队列
#1: [2]
#2: [3]
#3: [5]
#4: [1,5]
#5: [4,5]

应用

题目

leetcode 239. Sliding Window Maximum

解决方案

此题是单调优先队列的完美的应用场景，每次都要获取sliding window内的最大值。

解决方案也很简单，构建一个单调递减的优先队列，每次插入新加入sliding window 的元素，但是，有一点要注意，一定要删除已经移出sliding window的那个元素。

算法流程：

  1. 检查单调优先队列队首元素是否等于移出sliding window的那个元素，如果是那就弹出队首元素;
  2. 将新元素插入单调优先队列
  3. 将队首的最大元素插入到结果数组中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    	vector<int> ans;
    	deque<int> queue;
    	int i, size;
    	size = nums.size();
    	for(i = 0; i < size; ++i){
    		if(!queue.empty() && queue.front() == i-k){
    			queue.pop_front();
    		}
    		while(!queue.empty() && nums[queue.back()] < nums[i]){
    			queue.pop_back();
    		}
    		queue.push_back(i);
    		if(i >= k-1){
    			ans.push_back(nums[queue.front()]);
    		}
    	}
    	return ans;
    }
};

证明

问题是解决了，但是还是感觉心里不踏实，这样随便说两句总是难以说服自己算法 是正确的，所以还是证明一下比较靠谱。

要证明算法的正确性，也就是证明单调优先队列始终存储的是sliding window内的 元素，由于数组中的每个元素都会插入到单调优先队列中，所以只需证明单调优先队列 中保存的索引值始终都介于sliding window内。

方案中单调优先队列既保证了队列中元素的单调性又保证了元素所对应索引的单调性。 队列中所存储的索引单调递增，队列中索引所对应的值是单调递减的。

命题：单调优先队列中保存的索引值始终都介于sliding window内

使用数学归纳法(induction)。

1.当i=0时:

此时单调优先队列为空，单调优先队列中只会插入0，显然满足命题。

2.假设当i=m时，命题成立，那么当i=m+1时：

当i=m时，队列中所有元素x都满足m-k< x <= m，当插入第m+1个元素时，如果 队首元素等于m+1-k则弹出队首元素，否则就不弹出，这样就保证了队列中的所有元素 都满足m+1-k<x<=m+1。

综上所述，命题得证。

时间复杂度

利用摊还分析，数组中的每个元素最多只会进入队列一次和弹出一次，所以最坏的情况下 的时间复杂度为O(n)。