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.
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
;
o(n) time and O(k) memory
Solution:
1. 首先这道题最容易想到得是用heap做,维护一个heap,但是sliding window需要删除node,于是如果用HashHeap的话可以将时间复杂度降到O(nlogn). 即每次slide一次用logn时间添加结点再用logn时间删除结点。
2. 第二个方法是线性的 需要用到Deque即双端队列。比较难想到。
做法是:先考虑用stack,就是每次扫到新node时,先看stack.peek是不是比node小,如果小得话就把peek pop出去。直到peek比node小时,把node push进stack
然后此题因为需要每当slide window时,要把第一个数remove掉,这就需要用到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++) { addElement(deque, i, nums); } result.add(nums[deque.peekFirst()]); for (int i = 1; i < nums.length + 1 - k; i++) { removeElement(deque, i - 1); addElement(deque, i + k - 1, nums); result.add(nums[deque.peekFirst()]); } 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(); } }