力扣题目链接
(opens new window)
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
提示：文章来源：https://www.toymoban.com/news/detail-609008.html
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
代码文章来源地址https://www.toymoban.com/news/detail-609008.html
//解法一
//自定义数组
class MyQueue {
Deque<Integer> deque = new LinkedList<>();
//弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
//同时判断队列当前是否为空
void poll(int val) {
if (!deque.isEmpty() && val == deque.peek()) {
deque.poll();
}
}
//添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
//保证队列元素单调递减
//比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
void add(int val) {
while (!deque.isEmpty() && val > deque.getLast()) {
deque.removeLast();
}
deque.add(val);
}
//队列队顶元素始终为最大值
int peek() {
return deque.peek();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 1) {
return nums;
}
int len = nums.length - k + 1;
//存放结果元素的数组
int[] res = new int[len];
int num = 0;
//自定义队列
MyQueue myQueue = new MyQueue();
//先将前k的元素放入队列
for (int i = 0; i < k; i++) {
myQueue.add(nums[i]);
}
res[num++] = myQueue.peek();
for (int i = k; i < nums.length; i++) {
//滑动窗口移除最前面的元素，移除是判断该元素是否放入队列
myQueue.poll(nums[i - k]);
//滑动窗口加入最后面的元素
myQueue.add(nums[i]);
//记录对应的最大值
res[num++] = myQueue.peek();
}
return res;
}
}
//解法二
//利用双端队列手动实现单调队列
/**
* 用一个单调队列来存储对应的下标，每当窗口滑动的时候，直接取队列的头部指针对应的值放入结果集即可
* 单调队列类似 （tail -->） 3 --> 2 --> 1 --> 0 (--> head) (右边为头结点，元素存的是下标)
*/
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
int n = nums.length;
int[] res = new int[n - k + 1];
int idx = 0;
for(int i = 0; i < n; i++) {
// 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
// 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
while(!deque.isEmpty() && deque.peek() < i - k + 1){
deque.poll();
}
// 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offer(i);
// 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
if(i >= k - 1){
res[idx++] = nums[deque.peek()];
}
}
return res;
}
}
到了这里，关于239. 滑动窗口最大值的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
