[路飞]_leetcode-239-滑动窗口最大值

简介: leetcode-239-滑动窗口最大值

网络异常,图片无法展示
|


[题目地址][B站地址]


给你一个整数数组 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]
复制代码


示例 3:


输入: nums = [1,-1], k = 1
输出: [1,-1]
复制代码


示例 4:


输入: nums = [9,11], k = 2
输出: [11]
复制代码


示例 5:


输入: nums = [4,-2], k = 2
输出: [4]
复制代码


提示:


  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length


解题思路


本题是一个典型的维护区间最值的问题,那涉及维护区间最值的问题,可以利用 单调队列 解题。 如果你对 单调队列 还不了解,可以看我这一篇文章 数据结构-单调队列,文中介绍了单调队列的概念、应用场景及示例以及手写实现和示例问题求解的全过程。


代码实现


var maxSlidingWindow = function(nums, k) {
  // 初始化单调队列
  const queue = [],
  // 结果数组
  res = [];
  // 获取前k个元素的单调队列结果
  for(let i = 0;i<k;i++){
    while(queue.length&&nums[queue[queue.length-1]]<=nums[i]) queue.pop();
    queue.push(i);
  }
  // 将单调队列中的最大值插入结果数组
  res.push(nums[queue[0]])
  // 遍历后续输入数组,模拟窗口滑动过程
  for(let i = k;i<nums.length;i++){
    // 如果队首元素超出了滑动窗口的范围,删除队首元素
    if(queue[0]<=i-k) queue.shift();
    while(queue.length&&nums[queue[queue.length-1]]<=nums[i]) queue.pop();
    queue.push(i);
    // 将单调队列中的最大值插入结果数组
    res.push(nums[queue[0]])
  }
  // 返回结果数组
  return res;
};
复制代码


至此我们就完成了 leetcode-239-滑动窗口最大值


如有任何问题或建议,欢迎留言讨论!

相关文章
|
8月前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
3月前
【LeetCode 26】239.滑动窗口最大值
【LeetCode 26】239.滑动窗口最大值
45 1
|
3月前
【LeetCode 04】滑动窗口法总结
【LeetCode 04】滑动窗口法总结
33 0
|
5月前
|
存储 Python
【Leetcode刷题Python】239. 滑动窗口最大值
文章介绍了两种解决LeetCode上"滑动窗口最大值"问题的方法:使用大堆树和双向递减队列,提供了详细的解析和Python代码实现。
45 0
|
7月前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
42 1
|
7月前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
7月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
6月前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
7月前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
56 0
|
7月前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数