# Sliding Window Maximum

#### Sliding Window Maximum

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.

Example

For array `[1, 2, 7, 7, 8]`, moving window size `k = 3`. return `[7, 7, 8]`

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`;

Challenge

o(n) time and O(k) memory

Solution:

1. 首先这道题最容易想到得是用heap做，维护一个heap，但是sliding window需要删除node，于是如果用HashHeap的话可以将时间复杂度降到O(nlogn). 即每次slide一次用logn时间添加结点再用logn时间删除结点。

2. 第二个方法是线性的 需要用到Deque即双端队列。比较难想到。

```public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0 || nums.length < k) {
return result;
}
Deque<Integer> deque = new ArrayDeque<>();
deque.offerLast(0);
for (int i = 1; i < k; i++) {
}
for (int i = 1; i < nums.length + 1 - k; i++) {
removeElement(deque, i - 1);
addElement(deque, i + k - 1, nums);
}
return result;
}
//when adding a new element i,
//if nums[i]>=peakLast, we should keep popping the peak until the peak <nums[i]
//then we push nums[i]
public void addElement(Deque<Integer> deque, int index, int[] nums) {
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[index]) {
//pop the peak element
deque.pollLast();
}
deque.offerLast(index);
}

//when removing element, only check if the first of the deck is the same index
//then remove it. It is likely that it has already been popped out of the deque.
public void removeElement(Deque<Integer> deque, int index) {
if (index == deque.peekFirst()) {
deque.pollFirst();
}
}```

Share