博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LeetCode] Sliding Window Maximum 滑动窗口最大值
阅读量:6264 次
发布时间:2019-06-22

本文共 1780 字,大约阅读时间需要 5 分钟。

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,

Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max---------------               -----[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

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note: 

You may assume k is always valid, 1 ≤ k ≤ input array's size.

Follow up:

Could you solve it in linear time?

Hint:

  1. How about using a data structure such as deque (double-ended queue)?
  2. The queue size need not be the same as the window’s size.
  3. Remove redundant elements and the queue should store only elements that need to be considered.

这道题给定了一个数组,还给了一个窗口大小k,让我们每次向右滑动一个数字,每次返回窗口内的数字的最大值,而且要求我们代码的时间复杂度为O(n)。提示我们要用双向队列deque来解题,并提示我们窗口中只留下有用的值,没用的全移除掉。果然Hard的题目我就是不会做,网上看到了别人的解法才明白,解法又巧妙有简洁,膜拜啊。大概思路是用双向队列保存数字的下标,遍历整个数组,如果此时队列的首元素是i - k的话,表示此时窗口向右移了一步,则移除队首元素。然后比较队尾元素和将要进来的值,如果小的话就都移除,然后此时我们把队首元素加入结果中即可,参见代码如下:

class Solution {public:    vector
maxSlidingWindow(vector
& nums, int k) { vector
res; deque
q; for (int i = 0; i < nums.size(); ++i) { if (!q.empty() && q.front() == i - k) q.pop_front(); while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back(); q.push_back(i); if (i >= k - 1) res.push_back(nums[q.front()]); } return res; }};

本文转自博客园Grandyang的博客,原文链接:,如需转载请自行联系原博主。

你可能感兴趣的文章
python中获取指定目录下所有文件名列表的程序
查看>>
HTML5的本地存储 LocalStorage
查看>>
safari和ie的时间解析(显示为NAN)
查看>>
基于 HTML5 WebGL 的挖掘机 3D 可视化应用
查看>>
Java工具创建密钥库,用于Unity 3D打包、签名、发布
查看>>
Oracle用户解锁
查看>>
MongoDB的使用
查看>>
C#开启异步 线程的四种方式
查看>>
XML解析
查看>>
2784: 【提高】小 X 与煎饼达人(flip)
查看>>
Linux 常用的压缩命令有 gzip 和 zip
查看>>
内存分段与分页
查看>>
第一个WindowService服务
查看>>
zookeeper的三种安装模式
查看>>
腾讯2014实习面经 —— 面试经过回忆
查看>>
MIT Scheme 使用 Edwin
查看>>
BZOJ1500:[NOI2005]维修数列——题解
查看>>
transactionscope报“此操作对该事务的状态无效”问题
查看>>
css3(border-radius)边框圆角详解(转)
查看>>
[摘录]第2章 中场谈判技巧
查看>>