滑动窗口的最大值

2021-01-02

给你一个整数数组 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
通过次数96,586提交次数196,790

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

单调队列

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

        int end = 0;
        int index = 0;

        int[] res = new int[nums.length - k + 1];
        Deque<Integer> maxQueue = new LinkedList<>();

        maxQueue.offer(nums[0]);
        for (int i = 1; i < k; i++) {
            while (!maxQueue.isEmpty() && maxQueue.peekLast() < nums[i]) {
                maxQueue.pollLast();
            }
            maxQueue.offerLast(nums[i]);
        }
        res[index++] = maxQueue.peekFirst();

        end = k;                                                                              //定位到第一个窗口的末尾
        for (int i = 1; end < nums.length; i++, end++) {
            if (nums[i - 1] == maxQueue.peekFirst()) {
                maxQueue.pollFirst();
            }
            end = i + k - 1;
            while (!maxQueue.isEmpty() && maxQueue.peekLast() < nums[end]) {
                maxQueue.pollLast();
            }
            maxQueue.offerLast(nums[end]);
            res[index++] = maxQueue.peekFirst();
        }
        return res;
    }
}

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

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

优先队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        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];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

分块+预处理

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];
        for (int i = 0; i < n; ++i) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            }else {
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1 || (i + 1) % k == 0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        int[] ans = new int[n - k + 1];
        for (int i = 0; i <= n - k; ++i) {
            ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

单调队列(第二次做)

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] nums, int size) {
        int n = nums.length;
        
        ArrayList<Integer> res = new ArrayList<>();
        if(size==0||n<size||n==0)return res;
        LinkedList<Integer> queue = new LinkedList<>();
        LinkedList<Integer> maxQueue = new LinkedList<>();
        
        for(int i=0;i<size;i++){
            queue.offer(nums[i]);
            while(!maxQueue.isEmpty()&&maxQueue.peekLast()<nums[i]){
                maxQueue.pollLast();
            }
            maxQueue.offer(nums[i]);
        }
        
        for(int i=0;i<n-size+1;i++){
            res.add(maxQueue.peek());
            int del = queue.poll();
            if(maxQueue.peek()==del){
                maxQueue.poll();
            }
            
            int r = i + size;
            if(r>=n)break;
            queue.offer(nums[r]);
            while(!maxQueue.isEmpty()&&maxQueue.peekLast()<nums[r]){
                maxQueue.pollLast();
            }
            maxQueue.offer(nums[r]);
        }

        return res;
    }
}