Sliding Window Maximum-布布扣-bubuko.com

Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.

Input:
[1,2,7,7,8]
3
输出:
[7,7,8]

Explanation：
At first the window is at the start of the array like this `[|1, 2, 7| ,7, 8]` , return the maximum `7`;
then the window move one step forward.`[1, |2, 7 ,7|, 8]`, return the maximum `7`;
then the window move one step forward again.`[1, 2, |7, 7, 8|]`, return the maximum `8`;

Example 2:

Input:
[1,2,3,1,2,3]
5
Output:
[3,3]

Explanation:
At first, the state of the window is as follows: ` [,2,3,1,2,1 | , 3] `, a maximum of ` 3 `;
And then the window to the right one. ` [1, | 2,3,1,2,3 |] `, a maximum of ` 3

Challenge

o(n) time and O(k) memory

思路：单调的双端队列

public class Solution {
    /**
     * @param nums: A list of integers.
     * @param k: An integer
     * @return: The maximum number inside the window at each moving.
     */
    
    void inQueue(Deque<Integer> deque, int[]nums, int pos) {
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[pos]) {
            deque.pollLast();
        }
        deque.offer(pos);
    }
    
    void outQueue(Deque<Integer> deque, int pos) {
        if (deque.peekFirst() == pos) {
            deque.pollFirst();
        }
    }
    public List<Integer> maxSlidingWindow(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i <= k - 1; i++) {
            inQueue(deque, nums, i);
        }
        res.add(nums[deque.peekFirst()]);
        
        for (int i = k; i < nums.length; i++) {
            outQueue(deque, i - k);
            inQueue(deque, nums, i);
            res.add(nums[deque.peekFirst()]);
        }
        return res;
        
    }
}

Sliding Window Maximum

Description

Challenge