Leetcode-239-滑动窗口的最大值

Leetcode-239-滑动窗口最大值

题目描述

• 给你一个整数数组 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]

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

• 对于每个滑动窗口，我们可以使用 O(k) 的时间遍历其中的每一个元素，找出其中的最大值

• 对于长度为 n 的数组nums 而言，窗口的数量是 n - k + 1

• 因此算法的时间复杂度是 O((n - k + 1)k) = O(nk),会超出时间限制，因此我们需要进行一些优化。

• 对于两个相邻（只差了一个位置）的滑动窗口，它们共用着 k-1 个元素,而只有一个元素是变化的

方法一 ： 优先队列

• 对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。

• 对于本题而言

  • 初始时，我们将数组nums 的前k个元素都放入到优先队列中

  • 每当右移窗口的时候，我们就可以把一个新的元素放入到优先队列中，此时堆顶元素就是堆中所有元素的最大值。

  • 然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。

  • 这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。

  • 我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。

  • 为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组(num,index)，表示元素 num 在数组中的下标为 index。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 1. 优先队列存放的是二元组(num,index) : 大顶堆（元素大小不同按元素大小排列，元素大小相同按下标进行排列）
            // num :   是为了比较元素大小
            // index : 是为了判断窗口的大小是否超出范围
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] pair1,int[] pair2){
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0]:pair2[1] - pair1[1];
            }
        });

        // 2. 优选队列初始化 : k个元素的堆
        for(int i = 0;i < k;i++){
            pq.offer(new int[]{nums[i],i});
        }

        // 3. 处理堆逻辑
        int[] res = new int[n - k + 1];         // 初始化结果数组长度 ：一共有 n - k + 1个窗口
        res[0] = pq.peek()[0];                  // 初始化res[0] ： 拿出目前堆顶的元素
        for(int i = k;i < n;i++){               // 向右移动滑动窗口
            pq.offer(new int[]{nums[i],i});     // 加入大顶堆中
            while(pq.peek()[1] <= i - k){       // 将下标不在滑动窗口中的元素都干掉
                pq.poll();                      // 维护：堆的大小就是滑动窗口的大小
            }   
            res[i - k + 1] = pq.peek()[0];      // 此时堆顶元素就是滑动窗口的最大值
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O（nlogn）,其中 n 是数组nums的长度。

  • 在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。
  • 由于将一个元素放入优先队列的时间复杂度为 O(log*n)，因此总时间复杂度为 O(nlog*n)。

• 空间复杂度 ： O(n)，即为优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的 O(n)空间，只计算额外的空间使用。

打赏