Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Therefore, return the max sliding window as [3,3,5,5,6,7].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?
Solution1：Heap (max)
思路：維護一個大小為K的最大堆绽榛，依此維護一個大小為K的窗口贱勃，每次讀入一個新數(shù)盔腔，都把堆中窗口最左邊的數(shù)扔掉，再把新數(shù)加入堆中苏研，這樣堆頂就是這個窗口內(nèi)最大的值。
Time Complexity: O(NlogK) Space Complexity: O(K)
Solution：
思路： 遇到新的數(shù)時窝稿，
我們用雙向隊列可以在O(N)時間內(nèi)解決這題楣富。當我們遇到新的數(shù)時，將新的數(shù)和雙向隊列的末尾比較伴榔，如果末尾比新數(shù)小纹蝴，則把末尾扔掉庄萎，直到該隊列的末尾比新數(shù)大或者隊列為空的時候才住手。這樣塘安，我們可以保證隊列里的元素是從頭到尾降序的糠涛，由于隊列里只有窗口內(nèi)的數(shù)，所以他們其實就是窗口內(nèi)第一大兼犯，第二大忍捡，第三大...的數(shù)。保持隊列里只有窗口內(nèi)數(shù)的方法和上個解法一樣切黔，也是每來一個新的把窗口最左邊的扔掉砸脊，然后把新的加進去。然而由于我們在加新數(shù)的時候纬霞，已經(jīng)把很多沒用的數(shù)給扔了凌埂，這樣隊列頭部的數(shù)并不一定是窗口最左邊的數(shù)。這里的技巧是诗芜，我們隊列中存的是那個數(shù)在原數(shù)組中的下標瞳抓，這樣我們既可以直到這個數(shù)的值，也可以知道該數(shù)是不是窗口最左邊的數(shù)伏恐。這里為什么時間復(fù)雜度是O(N)呢孩哑？因為每個數(shù)只可能被操作最多兩次，一次是加入隊列的時候翠桦，一次是因為有別的更大數(shù)在后面横蜒，所以被扔掉，或者因為出了窗口而被扔掉秤掌。
Time Complexity: O(N) Space Complexity: O(N)
Solution1 Code：
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0) return new int[0];
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
int[] res = new int[nums.length + 1 - k];
for(int i = 0; i < nums.length; i++){
// 把窗口最左邊的數(shù)去掉
if(i >= k) pq.remove(nums[i - k]);
// 把新的數(shù)加入窗口的堆中
pq.offer(nums[i]);
// 堆頂就是窗口的最大值
if(i + 1 >= k) res[i + 1 - k] = pq.peek();
}
return res;
}
}
Solution2 Code：
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0) return new int[0];
LinkedList<Integer> deque = new LinkedList<Integer>();
int[] res = new int[nums.length + 1 - k];
for(int i = 0; i < nums.length; i++){
// 滑動窗: 每當新數(shù)進來時愁铺，如果發(fā)現(xiàn)隊列頭部的數(shù)的下標，是窗口最左邊數(shù)的下標闻鉴，則扔掉
if(!deque.isEmpty() && deque.peekFirst() == i - k) deque.poll();
// 把隊列尾部所有比新數(shù)小的都扔掉茵乱，保證隊列是降序的
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.removeLast();
// 加入新數(shù)
deque.offerLast(i);
// 隊列頭部就是該窗口內(nèi)第一大的
if((i + 1) >= k) res[i + 1 - k] = nums[deque.peek()];
}
return res;
}
}
