leetcode239.滑动窗口最大值

题目链接

解题思路一：最大堆

本题中，滑动窗口内的数字个数固定为k，从左依次滑动到右侧，要求返回滑动窗口的最大值，我们自然而然就可以想到使用最大堆这种数据结果解决这个问题。
代码如下：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        if(nums == null || nums.length == 0 || k == 0 || nums.length < k){
            return res;
        }
        // 建立建立最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return i2 - i1;
            }
        });
        for(int i = 0;i < nums.length;i++){
            if(maxHeap.size() >= k){
                maxHeap.remove(nums[i - k]);
            }
            maxHeap.offer(nums[i]);
            if(i >= k - 1){
                res[i - k + 1] = maxHeap.peek();
            }
        }
        return res;
    }
}

因为maxHeap.remove(nums[i - k]); 这个操作为O(k)的时间复杂度，所以该算法整体的复杂度为O(n*k);额外空间复杂度为O(k)
执行结果：

解题思路二：双端队列

本思路是使用双端队列，涉及到滑动窗口的问题都可以使用双端队列进行解决。
双端队列Deque用来保存窗口最大数值的index值
每次都是用队列的队尾与新进入的数字进行比较，如果队列队尾要比新的值小，那么就出队。

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

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

使用双端队列的时间复杂度为O(n),额外空间复杂度使用了双端队列这种数据结构，为O(k)
执行结果：