Day27_滑动窗口_剑指Offer

滑动窗口的最大值

给定一个数组 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。

解题思路

问题：

需要时刻记录当前窗口中的最大值
当窗口移动时需要考虑是否移除的是之前的最大值，以及插入的新值该排在什么位置
暴力算法会超时

实现：

使用双端队列存储最大值信息（存储：不严格递减存储，不符合的不存）利于删除头节点（最大值），添加删除尾节点（后续的大值）

例如：【1，6，5，2，5，3】，4 ，队列会存储【6，5，5，3】

移动时删除左端：如果左端值和队列头相同，队列弹出，下一个值作为队列头返回最大值
移动时添加右端：弹出双端队列中从队尾到队头所有小于添加节点的值，再添加节点，如上述例子下一步为：1，【6，5，2，5，3，4】，队列存储【6，5，5，4】弹出了3，添加了4
利用两个循环，一个用户创建基础滑动窗口，并获得对应初始队列；一个用于滑动运算

Java代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        int[] ans = new int[nums.length -k + 1];

        Deque<Integer> maxValue = new LinkedList<>();
        for(int i=0; i<k; i++) {
            while(!maxValue.isEmpty() && maxValue.peekLast() < nums[i]) maxValue.removeLast();
            maxValue.addLast(nums[i]);
        }
        ans[0] = maxValue.peekFirst();
        for(int i=k; i<nums.length; i++) {
            if(maxValue.peekFirst() == nums[i-k]) maxValue.removeFirst();
            while(!maxValue.isEmpty() && maxValue.peekLast() < nums[i]) maxValue.removeLast();
            maxValue.addLast(nums[i]);
            ans[i-k+1] = maxValue.peekFirst();
        }
        return ans;
    }
}

队列的最大值

medium 原题连接：队列的最大值

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例：

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

解题思路

和第一题很类似，是一个不固定长度的滑动窗口

数据信息和最大排序都是用双端队列存储，每次添加数据时做判断，弹出最大排序中所有小于插入值的值

获取最大值和弹出时额外判断是否为空即可

Java代码

class MaxQueue {
    Deque<Integer> numMessage;
    Deque<Integer> maxMessage;

    public MaxQueue() {
        numMessage = new LinkedList<>();
        maxMessage = new LinkedList<>();
    }
    
    public int max_value() {
        if(maxMessage.isEmpty()) return -1;
        return maxMessage.peekFirst();
    }
    
    public void push_back(int value) {
        numMessage.addLast(value);    
        while(!maxMessage.isEmpty() && maxMessage.peekLast() < value) maxMessage.removeLast();
        maxMessage.addLast(value);
    }
    
    public int pop_front() {
        if(numMessage.isEmpty()) return -1;
        if(maxMessage.peekFirst().equals(numMessage.peekFirst())) maxMessage.removeFirst();
        int ans = numMessage.peekFirst();
        numMessage.removeFirst();
        return ans;
    }
}

/**
 * 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();
 */