239. 滑动窗口最大值
思路一:(超时)
- 如果在最新的区间最右侧值C,比上一个区间最左侧的值A要大,则因为两者共用区间中最大值B一定比A要小,所以如果C比A大,则新区间最大值一定是C。
- 否则,我们就从头扫描这个区间得到最大值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int l = nums.length;
int[] res = new int[l-k+1];
int tmp = nums[0]; //因为nums.length>=1
for(int i=1;i<k;i++) // k<=l
tmp = Math.max(tmp,nums[i]);
res[0]=tmp;
for(int i=1;i<l-k+1;i++){
// 如果最大值是在新的区间里取到
if(nums[i+k-1]>=res[i-1])
res[i] = nums[i+k-1];
//否则,就是在找res[i,i+k-1]之中的最大值
else{
int tmp2 = nums[i];
for(int j=i+1;j<i+k;j++)
tmp2 = Math.max(tmp2,nums[j]);
res[i]=tmp2;
}
}
return res;
}
}
复杂度:
在最坏的情况下,即
A
>
C
A>C
A>C的情况下为
O
(
N
2
)
O(N^2)
O(N2)。
思路二:PriorityQueue(依旧超时)
在这里我们可以引入一个单调队列,每次保证它只有k个元素,这样每次添加和删除一个元素只要用 O ( l o g k ) O(logk) O(logk),一共进行 O ( n − k + 1 ) O(n-k+1) O(n−k+1)次操作,所以复杂度为 O ( n l o g k ) O(nlogk) O(nlogk)。
public int[] maxSlidingWindow(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(k,new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
return i2 - i1;
}
});
int l = nums.length;
int[] res = new int[l-k+1];
// 因为nums.length >= k
for(int i=0;i<k;i++)
pq.add(nums[i]);
res[0]=pq.peek();
for(int i=1;i<res.length;i++){
pq.remove(nums[i-1]);
pq.add(nums[i+k-1]);
res[i]=pq.peek();
}
return res;
}
思路三:用Deque实现的单调队列
思路:
我们用一个双向链表来存储数组中的下标,它满足如下的性质:
- ∀ i ≤ j , n u m s [ i ] ≥ n u m s [ j ] \forall i\leq j, nums[i]\geq nums[j] ∀i≤j,nums[i]≥nums[j]
因此,我们每次找最大值的时候,对于当前窗口[L,R],只要找 m i n { i ∈ deque 使得 L ≤ i ≤ R } min\{i \in \text{deque 使得} L \leq i\leq R\} min{i∈deque 使得L≤i≤R}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();
// 初始化第一个窗口
for (int i = 0; i < k; ++i) {
// 如[6,5,3,2] 加 4,则这个while会把原来的dequeue变成[6,5]
// 注意如果相等的话,我们也要取新的大一点的下标
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
// 删除多余的元素,这里的R=i,L=i-k+1 (出while循环下标i一定>i-k)
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}
Deque
// 初始化
Deque<Integer> deque = new LinkedList<Integer>();
// 添加元素 O(1)
deque.offerFirst(1);
deque.offerLast(2);
// 查看一个元素 O(1)
deque.peekFirst();
deque.peekLast();
// 删除一个元素 O(1)
System.out.println(deque.pollFirst());
System.out.println(deque.pollLast());
例子:
- 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
- 输出: [3,3,5,5,6,7]
- 初始状态:L=R=0,队列:{},其中L,R为当前窗口的下标。
i=0,nums[0]=1,队列为空,直接加入。队列:{0}
i=1,nums[1]=3,队尾值为nums[0]=1<3,所以弹出队尾值。队列:{1}
i=2,nums[2]=-1,队尾值为nums[1]=3>-1,直接加入,队列:{1,2} 此时窗口形成 L=0,R=2,result=nums[1]=3
i=3,nums[3]=-3,队尾值为nums[2]=-1>-3,直接加入,队列:{1,2,3} 此时L=1,R=3,nums[1]有效,result=[3,3]
i=4,nums[4]=5,队尾值为nums[3]=-3<5,依次弹出后加入,队列:{4} 此时L=2,R=4,nums[4]有效,result=[3,3,5]
i=5,nums[5]=3,队尾值为nums[4]=5>3,直接加入,队列:{4,5},此时L=3,R=5,nums[4]有效,result=[3,3,5,5]
i=6,nums[6]=6,队尾值为nums[5]=3<6,依次弹出后加入。队列:{6},此时L=4,R=6,nums[5]有效,result=[3,3,5,5,6]
i=7,nums[7]=7,队尾值为nums[6]=6<7,依次弹出后加入。队列:{7},此时L=5,R=7,nums[7]有效,result=[3,3,5,5,6,7]