剑指 Offer 59 - I. 滑动窗口的最大值
困难
632
相关企业
给定一个数组 nums 和滑动窗口的大小 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 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
提示：
你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length。
解法一：双端队列记录的是下标，而不是值（推荐！）
参考文献：左程云《程序员代码面试指南》
思路：
申请一个双端队列，我个人的理解是，它的作用是记录各个窗口的预备最大值；
设置好这个双端队列从前端出、从后端出的规则后，队首就是当前窗口的最大值。
具体地，因为窗口的长度是固定的，不妨假设窗口的右边界i遍历数组，
先看新元素nums[i]的插入规则,
为了维持“双端队列从头到尾元素（下标）所对应的nums值严格递减”，规定“如果deque.peekLast<=nums[i]，那么从后端弹出队尾元素，即deque.pollLast”，直到可以放i进双端队列deque为止;
下面介绍 过期元素（滑动窗口的老左边界）的弹出规则，
当过期元素正是双端队列的队首deque.peekFirst时，deque弹出此队首元素；
然后，如果已经形成了有效窗口（窗口长度为k），记录此次新窗口的最大值的下标，到res中。
public int[] maxSlidingWindow(int[] nums, int k) {// 我觉得这个代码更清晰、易懂
if(nums==null||nums.length==0){return new int[0];}
int[] res = new int[nums.length-k+1];
int index=0;// index used by 'res'
Deque<Integer> deque = new LinkedList<Integer>();
for(int i=0;i<nums.length;i++){// new window is [i-w+1,...,i]
// 清除障碍，准备加nums[i]进队列
while(!deque.isEmpty() && nums[deque.peekLast()]<=nums[i]){// 这里可以是<，也可以是<=
deque.pollLast();
}
deque.addLast(i);// 注意实际加进去的是下标，而不是值
// [i-k,..,i-1]------>[i-k+1,i]
// 窗口向右移动一格，老的左边界会出窗口，判断它是否是deque的队首，如果是，从头部弹出队首元素
if(deque.peekFirst()==i-k){
deque.pollFirst();
}
//record the max of this current slide window if it is formed well
if(i>=k-1){
res[i-k+1]=nums[deque.peekFirst()];
}
}
return res;
}
解法二：双端队列中记录的是数值，而不是下标
此时，注意安排好“什么时候才可以从队列尾部删除元素”。
参考链接
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length==0||k==0) return new int[0];
Deque<Integer> deque = new LinkedList<>();// deque
int[] res = new int[nums.length-k+1];
for(int l=1-k,r=0;r<nums.length;l++,r++){ // [l,..,r] is the current slideWindow
if( l>0&& deque.peekFirst()==nums[l-1]){
deque.removeFirst();
}
while(!deque.isEmpty()&&deque.peekLast()<nums[r]){ // big--->small
//注意：deque.peekLast()<nums[r] 不可以写成 deque.peekLast()<=nums[r]
// 解释见下面的注释
deque.removeLast();
}
deque.addLast(nums[r]);
if(l>=0){
res[l]=deque.peekFirst();
}
}
return res;
}
}
注：
有一个需要说明的地方是 while(!deque.isEmpty() && deque.peekLast() < nums[j])第二个判断必须是严格小于；否则，遇到含有重复数的测试用例时会出错。具体如：nums =[-7,-8,7,5,7,1,6,0]，k=4。如果写成“deque.peekLast() <= nums[j]”，那么第二个7进双端队列会把第一个7从队尾踢出来，之后滑动窗口右端到’6’（暂时还没有加’6‘）时，会出现问题——此时，双端队列的队首元素是第二个’7‘，而滑动窗口左边界也是’7‘（是第一个7），但是根据for循环中的第一个if语句（队首元素=窗口左边界元素 成立），会让此时双端队列的队首元素（第二个’7‘）从队首弹出，然后加入’6‘，记录双端队列的队首元素为’6‘到res数组中，视为此时滑动窗口的最大值，但这显然不对——此时滑动窗口【5,7,1,6】的最大值本应该是（原数组中第二个）’7‘。元凶就是，“deque.peekLast() <= nums[j]”，这会使得第一个’7‘过早地离开双端队列，而没有料理好自己的后事，第2个’7‘做了替罪羊。
滑动窗口的应用二：构建一个能O(1)返回最大值的队列
class MaxQueue {
LinkedList<Integer> main;
LinkedList<Integer> sub;// big--->small
public MaxQueue() {
main = new LinkedList<>();// main queue
sub=new LinkedList<>(); // subordinate queue
}
public int max_value() {
if(sub.isEmpty()) return -1;
return sub.peekFirst();
}
public void push_back(int value) {
main.addLast(value);
while(!sub.isEmpty()&&sub.peekLast()<value){
sub.pollLast();
}
sub.addLast(value);
}
public int pop_front() {
if(main.isEmpty()) return -1;
if(main.peekFirst().equals(sub.peekFirst())){ # !! dont use ==
sub.pollFirst();
}
return main.pollFirst();
}
}
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue obj = new MaxQueue();
* int param_1 = obj.max_value();
* obj.push_back(value);
* int param_3 = obj.pop_front();
*/
值得注意的是：
在pop_front这个方法中通过 d.peekFirst() == q.peek() 判断会得到错误的结果，因为 d.peekFirst() 和 q.peek()的返回值都是Integer类型，当数值在[-128,127]这样判断是没问题的，但是超出了这个范围Integer就会为他们分别创建对象。==本质是比较两个对象的引用是否相同，故会导致明明两个方法返回值相等但是==判断为false。
