239. 滑动窗口最大值 #
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[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
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
解答 #
1 暴力 #
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len=nums.length;
int[] res=new int[len-k+1];
int maxVal=-10001;
for(int i=0;i<k;i++){
maxVal=Math.max(nums[i],maxVal);
}
int resIndex=0;
for(int i=0;i<len-k+1;i++){
if(i!=0){
if(nums[i+k-1]>=maxVal){
maxVal=nums[i+k-1];
}else if(maxVal==nums[i-1]){
maxVal=nums[i];
for(int j=i;j<=i+k-1;j++){
maxVal=Math.max(nums[j],maxVal);
}
}
}
res[resIndex++]=maxVal;
}
return res;
}
}
超时
2 优先队列（堆） #
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len=nums.length;
int[] res=new int[len-k+1];
PriorityQueue<int[]> q=new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a,int[] b){
return b[0]-a[0];
}
});
for(int i=0;i<k;i++){
q.add(new int[]{nums[i],i});
}
int resIndex=0;
for(int i=0;i<len-k+1;i++){
if(i!=0){
q.add(new int[]{nums[i+k-1],i+k-1});
while(q.peek()[1]<=i-1){
q.poll();
}
}
res[resIndex++]=q.peek()[0];
}
return res;
}
}
需要保留nums[i] & i(下标)，判断如果是最大值的下标已经从滑动窗口中离开的话，这个最大值就删除。 还需要注意优先队列的排序问题
复杂度分析
- 时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)。
- 空间复杂度：O(n)，即为优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的 O(n) 空间，只计算额外的空间使用。
3 单调队列 #
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
Deque<Integer> q = new ArrayDeque<>();
int[] res = new int[len - k + 1];
int resIndex = 0;
for (int i = 0; i < k; i++) {
while (!q.isEmpty() && nums[q.getFirst()] <= nums[i]) {
q.removeFirst();
}
q.addFirst(i);
}
for (int i = 0; i < len - k + 1; i++) {
if (i != 0) {
while (!q.isEmpty() && nums[q.getFirst()] <= nums[i+k-1]) {
q.removeFirst();
}
q.addFirst(i+k-1);
while(!q.isEmpty() && q.getLast()<=i-1){
q.removeLast();
}
}
res[resIndex++] = nums[q.getLast()];
}
return res;
}
}
队列维护起来就是一个单调递减的队列，队尾的值是最大的，入队的话，从队头开始进入，并且满足递减的特性，这样维护队列可以快速找出最大值。
- 维护双端队列： 使用双端队列 (deque) 存储数组的索引，并组织这些索引以保持递减的顺序。
- 滑动窗口： 代码旨在为每个窗口找到最大值。它遍历数组，将元素添加到双端队列中。
- 双端队列更新：
- 移除元素： 如果将一个元素添加到双端队列中，代码会检查它的值是否大于当前元素。如果大于，则从双端队列中移除较小的元素。这是因为如果一个元素小于队列中当前元素，则不需要保留较小的元素。
- 滑动窗口更新： 代码会检查最左侧元素的索引是否仍在当前窗口内，如果不在，则将其移除。这是因为窗口从左侧向前滑动，因此会添加一个新元素。
- 返回值：
- 代码返回当前滑动窗口的最大值。
单调队列套路
- 入（元素进入队尾，同时维护队列单调性）
- 出（元素离开队首）
- 记录/维护答案（根据队首）
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组 nums 的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)。
- 空间复杂度：O(k)。与方法一不同的是，在方法二中我们使用的数据结构是双向的，因此「不断从队首弹出元素」保证了队列中最多不会有超过 k+1 个元素，因此队列使用的空间为 O(k)。