leetCode-239:Sliding Window Maximum

问题描述

给定一个整数数组和一个表示窗口大小的正整数 k（ k 小于数组长度），窗口从数组左侧向右滑动，要求找出每个滑动窗口期间内数字的最大值。题目链接：**点我**

样例输入输出

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

输出：[3,3,5,5,6,7]

解释：

Window position     Max

[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

输入：nums = [1,2,3], k = 3

输出：[3]

问题解法

解法一：大顶堆

使用大顶堆（优先队列）来存储数据，窗口滑动时，将当前值放入堆中，同时取出堆顶的元素，如果元素已经不在窗口范围内，则移除，如果元素在窗口范围内，则放如结果数组中。由于要进行堆顶元素和窗口边界的判断，所以此处需要同时在优先队列中存储数组的元素（用于优先队列比较大小）和元素的下标（用于比较堆顶元素是否在滑动窗口内）。代码如下

class Solution
{
    public int[] maxSlidingWindow(int[] nums, int k)
    {
        Queue<int[]> queue = new PriorityQueue<>(k, (o1, o2) -> o2[1] - o1[1]);
        for (int i = 0; i < k - 1; i++)
        {
            queue.offer(new int[]{i, nums[i]});
        }

        int[] result = new int[nums.length - k + 1];
        for (int i = k - 1; i < nums.length; i++)
        {
            queue.offer(new int[]{i, nums[i]});
            while (queue.peek()[0] < i - k + 1)
            {
                queue.poll();
            }
            result[i - k + 1] = queue.peek()[1];
        }

        return result;
    }
}

解法二：双端队列

此解法参考：https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/。使用一个队列来存储元素的下标，同时用类似单调递减栈的思想，每次遍历数组元素，如果队列尾部指向的数字小于当前数字，则将队尾元素出队，同时判断队首的元素是否在滑动窗口范围内，如果不在，则将队首元素出队。这样处理过后，队列中每个元素指向的数字是依次递减的，并且队首的元素指向的数字就是当前滑动窗口内的最大数字。代码如下

class Solution
{
    public int[] maxSlidingWindow(int[] nums, int k)
    {
        LinkedList<Integer> queue = new LinkedList<>();
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++)
        {
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i])
            {
                queue.pollLast();
            }

            queue.offerLast(i);
            while (!queue.isEmpty() && queue.peekFirst() < i + 1 - k)
            {
                queue.pollFirst();
            }

            if (i + 1 >= k)
            {
                result[i + 1- k] = nums[queue.peekFirst()];
            }
        }

        return result;
    }
}

参考资料

https://leetcode-cn.com/problems/sliding-window-maximum/solution/shuang-xiang-dui-lie-jie-jue-hua-dong-chuang-kou-2/