Day27_滑动窗口_剑指Offer
IT蛋
2023-04-18 22:35
阅读2240
滑动窗口的最大值
Hard 原题连接：滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例：
输入: 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
提示：
- 你可以假设 k 总是有效的，在输入数组 不为空 的情况下，1 ≤ k ≤ nums.length。
解题思路
问题：
- 需要时刻记录当前窗口中的最大值
- 当窗口移动时需要考虑是否移除的是之前的最大值，以及插入的新值该排在什么位置
- 暴力算法会超时
实现：
- 使用双端队列存储最大值信息（存储：不严格递减存储，不符合的不存）利于删除头节点（最大值），添加删除尾节点（后续的大值）
例如： 【1，6，5，2，5，3】，4 ，队列会存储【6，5，5，3】
- 移动时删除左端：如果左端值和队列头相同，队列弹出，下一个值作为队列头返回最大值
- 移动时添加右端：弹出双端队列中从队尾到队头所有小于添加节点的值，再添加节点，如上述例子下一步为：1，【6，5，2，5，3，4】，队列存储【6，5，5，4】弹出了3，添加了4
- 利用两个循环，一个用户创建基础滑动窗口，并获得对应初始队列；一个用于滑动运算
Java代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k == 0) return new int[0];
int[] ans = new int[nums.length -k + 1];
Deque<Integer> maxValue = new LinkedList<>();
for(int i=0; i<k; i++) {
while(!maxValue.isEmpty() && maxValue.peekLast() < nums[i]) maxValue.removeLast();
maxValue.addLast(nums[i]);
}
ans[0] = maxValue.peekFirst();
for(int i=k; i<nums.length; i++) {
if(maxValue.peekFirst() == nums[i-k]) maxValue.removeFirst();
while(!maxValue.isEmpty() && maxValue.peekLast() < nums[i]) maxValue.removeLast();
maxValue.addLast(nums[i]);
ans[i-k+1] = maxValue.peekFirst();
}
return ans;
}
}
队列的最大值
medium 原题连接：队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例：
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]位有符号整数范围。
因此返回 INT_MIN (−231) 。
解题思路
和第一题很类似，是一个不固定长度的滑动窗口
数据信息和最大排序都是用双端队列存储，每次添加数据时做判断，弹出最大排序中所有小于插入值的值
获取最大值和弹出时额外判断是否为空即可
Java代码
class MaxQueue {
Deque<Integer> numMessage;
Deque<Integer> maxMessage;
public MaxQueue() {
numMessage = new LinkedList<>();
maxMessage = new LinkedList<>();
}
public int max_value() {
if(maxMessage.isEmpty()) return -1;
return maxMessage.peekFirst();
}
public void push_back(int value) {
numMessage.addLast(value);
while(!maxMessage.isEmpty() && maxMessage.peekLast() < value) maxMessage.removeLast();
maxMessage.addLast(value);
}
public int pop_front() {
if(numMessage.isEmpty()) return -1;
if(maxMessage.peekFirst().equals(numMessage.peekFirst())) maxMessage.removeFirst();
int ans = numMessage.peekFirst();
numMessage.removeFirst();
return ans;
}
}
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue obj = new MaxQueue();
* int param_1 = obj.max_value();
* obj.push_back(value);
* int param_3 = obj.pop_front();
*/
评论
问答助学
相关内容
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
内容推荐
刷题经验分享
60
Leetcode文章资源分享：高效刷满500题方法论
170
这几天刷题算法，我也是入门基础，虽然还是难，思路啥的，但是温习了很多，比如map集合的containsKey等等 set的去重 map的计数等等今天刷了一道算法中等二维数组的 零矩阵 虽然还是查阅了资料但是没看题解，就是二维数组的列长度计算。。跌跌撞撞终于写出了一道中等题目[流泪][流泪]，，很开心。想放弃的，但是写出来那种成就感很足，继续加油吧[呲牙]
10
才发现力扣评论区也显示ip属地了，是从今天还是昨天开始的，刚注意到[捂脸]
15
学习总结 Python 算法 前端关于过去一年的学习情况去年尝试学习了MCU学了有一周左右弃了，然后抄网上的flask框架的项目，搞到一半发现有一些前端的问题不怎么明白，然后开始刷前端当前学到BOM，然后是算法刷了100多道 目前除了动态规划不怎么行 其他题目看到都还有点思路
8
