[LeetCode] Sliding Window Maximum

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 slidi

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.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

Hint:

How about using a data structure such as deque (double-ended queue)? The queue size need not be the same as the window’s size. Remove redundant elements and the queue should store only elements that need to be considered.

依据提示，借助一个deque来实现，deque里面存储可能的最大值的下标。遍历数组，若当前元素大于队列尾部元素，则移除尾部元素，然后添加当前元素的下标。提取deque中的值时，需要考虑deque首部的值是否在当前元素的窗口内。

private Deque Integer deque = new LinkedList Integer public int[] maxSlidingWindow(int[] nums, int k) { if (k == 0) { return new int[0]; int[] res = new int[nums.length - k + 1]; for (int i = 0; i nums.length; i++) { while (!deque.isEmpty() nums[i] = nums[deque.peekLast()]) { deque.pollLast(); deque.offerLast(i); while (deque.peekFirst() i - k + 1) { deque.pollFirst(); if (i = k - 1) { res[i - k + 1] = nums[deque.peekFirst()]; return res; }