Sliding Window Maximum

Leave a comment

October 30, 2016 by oneOokay

写了个暴力解法O(mk)过了。暴力解法大家应该都能写到,但是这个题目考的是另外的优化解法,有两种:max heap和双向队列(DEQUE)。https://segmentfault.com/a/1190000003903509

所以暴力解法的两个for-loop,要想办法只用一个for-loop,那么在求整个window中的max这里,就需要是一个O(1)。

发现以前做过一个最小栈,跟这个可能没什么关系,但是可以看一下刷新一下记忆。

MAX HEAP:

“堆”是priority queue based on priority heap. 默认排序是最小值为head,位于顶端。priority queue里不允许null。PriorityQueue O(logn)的enqueue dequeue时间。所以一下的时间复杂度是O(nlogn).空间复杂度是O(n).

public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0 || k == 0) {
return new int[0];
}
int[] ans = new int[nums.length - k + 1]; //这题要注意下标。
PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); 
//让priority queue的最大值位于顶部。
for (int i = 0; i < nums.length; i ++) {
pq.offer(nums[i]); //把每一个值都放入priority queue中
if (i < k - 1) { //如果i < k -1 : 第一个窗户都还没有填满,什么都不做,继续填
continue;
}
if (i > k - 1) { //填已经超过第一个窗户了,所以要把最左边的元素移除。
pq.remove(nums[i - k]); 
//priority queue.remove(e): 移除priority queue中的e元素
}
ans[i - k + 1] = pq.peek(); 
//刚好填满一个窗户的时候,不需要移除任何元素,直接peek()顶端为最大值。
//填超过一个窗户,前面已经把最左的元素移除了,所以该窗户的最大值就也是在顶端了。
}
return ans;
}

DEQUE: 双向队列:A linear collection that supports element insertion and removal at both ends.  “double ended queue”. pronunciation: “deck”.

Deque和Queue的时间复杂度是一样的:Acess和Search O(n) Insert和Delete是O(1)

Deque deque = new LinkedList()
First Element (Head) Last Element (Tail)
Throws exception Special value Throws exception Special value
Insert addFirst(e) offerFirst(e) addLast(e) offerLast(e)
Remove removeFirst() pollFirst() removeLast() pollLast()
Examine getFirst() peekFirst() getLast() peekLast()

思路是:构造一个双向队列,队列中的数字是从head至tail递减,所以当queue.peekFirst()的时候,得到的是最大值。

具体:每加入一个新的值的时候:

  1. 首先看双向队列的head是否是上一个窗户的最左边的元素。如果是的话,就要把它扔掉。因为加入这个数字之后,head的元素就不在窗户范围内了,所以不在最大值的考虑范围内。
  2. 其次将要加入的这个值与tail的值对比,如果tail的值比该值小,那么把tail扔掉。一直到队列为空或者tail的值比该值大为止。
  3. 加入该值。如此保证了队列的递减。
  4. peekFirst加入到ans里。

时间复杂度是O(n):每个数最多可备操作两次,加入queue,移出queue。被扔掉之后就不会再被处理了。

public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0 || k == 0) {
return new int[0];
}
int[] ans = new int[nums.length - k + 1];
Deque queue = new LinkedList();
for (int i = 0; i < nums.length; i ++) {
if (!queue.isEmpty() && queue.peekFirst() == i - k) { //step1.
queue.poll(); //poll的时候是poll head的值。也就是poll peek的值。
}
while (!queue.isEmpty() && queue.peekLast() < nums[i]) { //step2.
queue.removeLast();
}
queue.offerLast(nums[i]);//step3.
if ( i + 1 > k ) {
res[i - k + 1] = queue.peekFirst(); //step4.
}}
return ans;
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: