Description
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;
}
}