LeetCode 滑动窗口最大值【滑动窗口】

秒速五厘米 2022-09-10 11:26 166阅读 0赞

# 1 滑动窗口最大值 #

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

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

**示例 1：**

输入：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

**示例 2：**

输入：nums = [1], k = 1
    输出：[1]

**示例 3：**

输入：nums = [1,-1], k = 1
    输出：[1,-1]

**示例 4：**

输入：nums = [9,11], k = 2
    输出：[11]

**示例 5：**

输入：nums = [4,-2], k = 2
    输出：[4]

# 2 解题思路 #

## 2.1 双向队列 ##

public int[] maxSlidingWindow(int[] nums, int k) { 
            int[] rs = new int[nums.length - k + 1];
            //双向队列
            Deque<Integer> queue = new LinkedList<>();
            //初始化双向队列，队列按递减存入
            for (int i = 0; i < k; i++) { 
                while (!queue.isEmpty() && nums[queue.getLast()] < nums[i]) { 
                    queue.removeLast();
                }
                queue.addLast(i);
            }
    
            int index = 0;
            rs[index++] = nums[queue.getFirst()];
    
            for (int i = k; i < nums.length; i++) { 
                //上一个窗口的最大值需要删除
                if (queue.getFirst() == i - k) { 
                    queue.removeFirst();
                }
                //移除小的
                while (!queue.isEmpty() && nums[queue.getLast()] < nums[i]) { 
                    queue.removeLast();
                }
                queue.addLast(i);
                rs[index++] = nums[queue.getFirst()];
            }
    
            return rs;
        }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5L2g5pC656eL5pyI5o-95pif5rKz5Li2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/42ea1ca1d76e4c3ebdc0f0fb2f3763f3.png