239. 滑动窗口最大值

柔情只为你懂 2023-10-14 08:38 15阅读 0赞

### 239. 滑动窗口最大值 ###

*  题干背景
 *  解题思路
 *   *  不能使用大顶堆的原因
     *  希望实现的数据结构
     *  自己实现该队列的关键点
     *  设计的队列规则
     *  使用的数据结构
 *  代码实现
 *   *  解法一（自定义递减数组）
     *  解法二 （利用双端队列手动实现单调队列）

# 题干背景 #

[力扣入口 - 239. 滑动窗口最大值][- 239.]

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

![在这里插入图片描述][49e7172936e945c3941837986d28ce61.png]

# 解题思路 #

## 不能使用大顶堆的原因 ##

有人可能会想用一个大顶堆（优先级队列）来存放这个窗口里的k个数字，这样就可以知道最大的最大值是多少了， 但是问题是这个窗口是移动的，而大顶堆每次只能弹出最大值，我们无法移除其他数值，这样就造成大顶堆维护的不是滑动窗口里面的数值了。所以不能用大顶堆。

## 希望实现的数据结构 ##

我们需要一个队列，这个队列放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。

这个队列应该长这个样子：

class MyQueue {
        
    public:
        void pop(int value) {
        
        }
        void push(int value) {
        
        }
        int front() {
        
            return que.front();
        }
    };

每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.front()就返回我们要的最大值。

## 自己实现该队列的关键点 ##

1.  队列里的元素一定是要排序的，而且要最大值放在出队口，要不然怎么知道最大值呢。
2.  其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

## 设计的队列规则 ##

1.  pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。
2.  push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止。

## 使用的数据结构 ##

使用deque最为合适，常用的queue在没有指定容器的情况下，deque就是默认底层容器。

# 代码实现 #

## 解法一（自定义递减数组） ##

class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
        
            if(nums.length == 1){
        
                return nums;
            }
            int len = nums.length - k + 1;
            // 存放结果元素的数组
            int[] res = new int[len];
            int num = 0;
            // 自定义单调数组
            MonoQue monoQue = new MonoQue();
            // 先将前k的元素放入队列
            for(int i = 0; i < k; i++){
        
                monoQue.add(nums[i]);
            }
            res[num++] = monoQue.peek();
            for(int i = k; i < nums.length; i++){
        
                // 滑动窗口移除最前面的元素，移除是判断该元素是否放入队列
                monoQue.poll(nums[i - k]);
                // 滑动窗口加入最后面的元素
                monoQue.add(nums[i]);
                // 记录对应的最大值
                res[num++] = monoQue.peek();
            }
            return res;
        }
    }
    
    class MonoQue {
        
        Deque<Integer> deque = new LinkedList<>();
        // 弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
        // 同时判断队列当前是否为空
        void poll(int val){
        
            if(!deque.isEmpty() && val == deque.peek()){
        
                deque.poll();
            }
        }
        // 添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
        // 保证队列元素单调递减
        // 比如此时队列元素3, 1, 2将要入队，比1大，所以1弹出，此时队列：3, 2
        void add(int val){
        
            while(!deque.isEmpty() && val > deque.getLast()){
        
                deque.removeLast();
            }
            deque.add(val);
        }
        // 队列队顶元素始终为最大值
        int peek(){
        
            return deque.peek();
        }
    }

## 解法二 （利用双端队列手动实现单调队列） ##

/**
     * 用一个单调队列来存储对应的下标，每当窗口滑动的时候, 直接取队列的头部指针对应的值放入结果集即可
     * 单调队列类似（tail -->）3 --> 2 --> 1 --> 0 (--> head) (右边为头结点, 元素存的是下标)
     */
    public int[] maxSlidingWindow2(int[] nums, int k){
        
    	ArrayDeque<Integer> deque = new ArrayDeque<>();
    	int n = nums.length;
    	int[] res = new int[n-k+1];
    	int idx = 0;
    	for(int i = 0; i < n; i++){
        
    		// 根据题意，i为nums下标，是要在[i-k+1, i]中选到最大值，只需要两点
    		// 1. 队列头结点需要在[i-k+1, i]范围内, 不符合则要弹出
    		while(!deque.isEmpty() && deque.peek() < i-k+1){
        
            	deque.poll();
            }
            // 2. 既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
        
                deque.pollLast();
            }
            deque.offer(i); // offer()方法用于在双端队列的末尾添加给定元素。
    	    // 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
            if(i >= k - 1){
        
                res[idx++] = nums[deque.peek()];
            }
    	}
        return res;
    }

**参考资料**：[239. 滑动窗口最大值][239.]

[- 239.]: https://leetcode.cn/problems/sliding-window-maximum/
[49e7172936e945c3941837986d28ce61.png]: https://img-blog.csdnimg.cn/49e7172936e945c3941837986d28ce61.png
[239.]: https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html#google_vignette