Sliding Window Maximum 单调队列解区间最值
经典面试问题, 终于出现在Leetcode了, 写完后看了下discuss, 基本大家写的都差不多. 可见这题多容易考, 我身边的朋友就有被问过这题的.
题目很简单, 就是给一个大小为k的窗口, 然后给一个数组, 问在k下的最值是什么. 就用Leetcode的例子吧.
单调队列解区间最值
nums 输入数组
k 队列窗口大小
Given nums = [1,3,-1,-3,5,3,6,7], and k = 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
这题的解法好像有两种, 一种是双指针, 另一种是单调队列, 双指针判断corn case很复杂, 所以用单调队列比较简单, 代码短,面试才不容易出错.
单调队列是一个单调递增(递减)的队列, 这题中, 单调队列的大小为k.需要注意一下几点:
- 单调队列是一个双向队列, 所以可以用Dequeue 或者直接用LinkedList实现.
- 添加元素时, 从右(last) 往左(first) 添加, 添加的是数组的index, 因为下边我们需要通过比较index, 来判断是否过期.
- 添加元素前, 需要删除过期元素, 当判断一个元素是否过期时, 要从前往后判断, 因为前边的元素是队列中时序最”老”的元素. 并且判断时, 要比较最老元素的index和i-k+1的大小. i – k + 1是窗口[i-k+1,i]的最左边的index, 比如, 当i=6, 即在第6个元素时, 窗口左边的index为6-3+1 = 4, 所以窗口内最大可能的元素index为[4,5,6]
- 添加元素前, 需要删除比当前元素小的元素, 我们需要从队列的右边往左边 踢出元素, 因为队列是单调的, 右边的元素小于左边的元素. 所以通过踢出右边小于当前元素的元素, 保持队列单调.
代码如下:
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0 || nums == null)
return new int[]{};
int n = nums.length;
int[] res = new int[n - k + 1]; // 结果
int p = 0;
LinkedList<Integer> queue = new LinkedList<Integer>(); // 双向queue, 这里用linkedlist了. 也可以用Dequeue
for (int i = 0; i < nums.length; i++) {
//窗口大小为k, 所以 i-k+1为在位置i上的窗口, 踢出所有窗口外的元素, 因为队列是从尾部添加的, 所以我们踢出头部的元素
while (!queue.isEmpty() && queue.peekFirst() < i - k + 1)
queue.removeFirst();
//踢出所有小于当前元素的元素, 这里要从尾部踢出, 是因为尾部的元素是按照扫描的顺序添加的并且,大小为递减添加的.
while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i])
queue.removeLast();
// 添加到尾部.
queue.addLast(i);
if (i >= k-1)// 当窗口未完全展开时, 不记录元素.
res[p++] = nums[queue.peekFirst()];
}
return res;
}
Leave A Comment