LeetCode Hot100 239.滑动窗口最大值
2023-12-18 18:57:10
题目:
给你一个整数数组?nums
,有一个大小为?k
?的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的?k
?个数字。滑动窗口每次只向右移动一位。
返回?滑动窗口中的最大值?。
思路:
代码:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n - k + 1]; // 记录结果
Deque<Integer> q = new ArrayDeque<>(); // 双端队列 队首到队尾是递减的
for (int i = 0; i < n; i++) {
// 1.入
while (!q.isEmpty() && nums[q.getLast()] <= nums[i]) {
q.removeLast(); // 维护q的单调性
}
q.addLast(i); // 入队
// 2.出( 弹出队首不在窗口内的元素 )
if (i - q.getFirst() >= k) {
q.removeFirst();
}
// 3.记录答案
if (i >= k - 1) {
// 由于队首到队尾单调递减,所以窗口最大值就是队首
ans[i - k + 1] = nums[q.getFirst()];
}
}
return ans;
}
}
滑动窗口问题三部曲:
1、入
2、出
3、记录答案
文章来源:https://blog.csdn.net/qq_57349657/article/details/135068132
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!