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 sizek = 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 maximum7
;
then the window move one step forward.
[1, |2, 7 ,7|, 8]
, return the maximum7
;
then the window move one step forward again.
[1, 2, |7, 7, 8|]
, return the maximum8
;
分析
Deque双端队列, deque就是linkedlist ,deque 两头都可进可出 ,deque里元素单调递减
Deque offer,add加入末尾,push加入头
O(N*K),每个元素都push 和pop一次 2n,所以是O(N)
用Deque双端队列来解。分为添加元素和删除元素两部步。
初始化第一个窗口(0-第k-1个元素),一次向deque中加入数组中的元素。每次加入新元素时,若deque中最后一个元素比新元素小,则删去,直到deque中最后一个元素比新元素大时停止(或deque为空时停止),然后加入新元素。
添加元素:从第k的元素开始,每次加入新元素时,若deque中最后一个元素比新元素小,则删去,直到deque中最后一个元素比新元素大时停止(或deque为空时停止),然后加入新元素。此时deque中第一个元素即为当前窗口的最大值,加入答案中。
删除元素:应该删去(当前位置-k)位置的元素,看deque第一个元素是否和要删除元素相等,若不相等则说明在之前的元素加入过程中该元素已经删去,则不用做任何操作,否则删去deque中第一个元素即可。
public class Solution {
/**
* @param nums: A list of integers.
* @return: The maximum number inside the window at each moving.
*/
private void inQueue(Deque<Integer> q, int num){
while(!q.isEmpty() && q.peekLast() < num){
q.pollLast();
}
q.offer(num);
}
private void outQueue(Deque<Integer> q, int num){
if(num == q.peekFirst()){
q.pollFirst();
}
}
public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
// write your code here
int n = nums.length;
Deque<Integer> q = new ArrayDeque<Integer>();
ArrayList<Integer> ret = new ArrayList<Integer>();
if(n == 0)
return ret;
//只到k-1因为k开始需要取结果了,之前不需要取只需要加数字
for(int i = 0; i < k-1; i ++){
inQueue(q, nums[i]);
}
for(int i = k-1; i < n; i ++){
inQueue(q, nums[i]);
ret.add(q.peekFirst());
outQueue(q, nums[i-k+1]);
}
return ret;
}
}
python
入列:维持递减队列(每个数进入dp,把比他小的都弹出),最大的总在队首,每次队首加入res
出列:队首和nums[i-k+1]比较,==就弹出,不是的话证明dp size不够K,不必弹
双端队列(Deque),可以维持一个递增的双端队列
EX:[|1, 4|, 5, 3, 9], k = 3
我们先将k-1个元素放入队列:|2|
然后从第k个元素开始,一次加入新元素并删除旧元素,并且保持滑动窗口的size不变
[|1, 4, 5|, 3, 9], Deque: 5, Output: [5];
[1, |4, 5, 3|, 9], Deque: 5, 5, Output: [5, 5];
[1, 4, |5, 3, 9|], Deque: 8, Output: [5, 5, 8];
因为对于每个数组中的元素只扫描一次,所以总体时间在deque操作中也近似于线性,所以总运行时间:O(n)(amortized), 空间复杂度:O(1)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums:
return []
dq = collections.deque()
for i in range(k-1):
self.inQueue(dq, nums[i])
l = len(nums)
res = []
for i in range(k-1, l):
self.inQueue(dq, nums[i])
res.append(dq[0])
self.outQueue(dq, nums[i-k+1])
return res
def inQueue(self, dq:collections.deque, k: int):
while dq and dq[-1] < k:
dq.pop()
dq.append(k)
def outQueue(self, dq:collections.deque, k: int):
if dq[0] == k:
dq.popleft()
Last updated
Was this helpful?