题目描述

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Follow up:
Could you solve it in linear time?

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

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

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

算法1

(单调队列) O(n)

Java 代码

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return new int[]{};
        }

        int res[] = new int[n - k + 1];
        Deque<Integer> queue = new ArrayDeque<>();

        for (int i = 0, j = 0; i < n; i++) {
            // 检查滑动窗口
            while (!queue.isEmpty() && i - k + 1 > queue.getFirst()) {
                queue.pollFirst();
            }

            // 检查单调性,递减队列
            while (!queue.isEmpty() && nums[i] > nums[queue.getLast()]) {
                queue.pollLast();
            }

            // 新的符合条件的数字入队列
            queue.offer(i);

            // 前k个不计入结果数组
            if (i - k + 1 >= 0) {
                res[j++] = nums[queue.getFirst()];
            }
        }

        return res;
    }
}