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即双端队列。比较难想到。

做法是:先考虑用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();
    }
}

 

FacebookTwitterGoogle+Share