题目描述：
给出一个可能包含重复的整数数组，和一个大小为 k 的滑动窗口, 从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值。
样例：
给出数组 [1,2,7,7,8], 滑动窗口大小为 k = 3. 返回 [7,7,8].
解释：
最开始，窗口的状态如下：[|1, 2 ,7| ,7 , 8], 最大值为 7;
然后,窗口向右移动一位：[1, |2, 7, 7|, 8], 最大值为 7;
最后,窗口再向右移动一位：[1, 2, |7, 7, 8|], 最大值为 8。
代码实现：
public class Solution {
/**
* @param nums: A list of integers.
* @return: The maximum number inside the window at each moving.
*/
void inQueue(Deque<Integer> deque, int num) {
while (!deque.isEmpty() && deque.peekLast() < num) {
deque.pollLast();
}
deque.offer(num);
}
void outQueue(Deque<Integer> deque, int num) {
if (deque.peekFirst() == num) {
deque.pollFirst();
}
}
public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
ArrayList<Integer> ans = new ArrayList<Integer>();
Deque<Integer> deque = new ArrayDeque<Integer>();
if (nums.length == 0) {
return ans;
}
for (int i = 0; i < k - 1; i++) {
inQueue(deque, nums[i]);
}
for(int i = k - 1; i < nums.length; i++) {
inQueue(deque, nums[i]);
ans.add(deque.peekFirst());
outQueue(deque, nums[i - k + 1]);
}
return ans;
}
}
