当前位置:网站首页>239. 滑动窗口最大值(困难)-单向队列、大顶堆-字节跳动高频题
239. 滑动窗口最大值(困难)-单向队列、大顶堆-字节跳动高频题
2022-04-23 17:32:00 【hequnwang10】
一、题目描述
给你一个整数数组 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]
二、解题
单向队列
首先这题需要注意两个点
- 维护滑动窗口长度值,滑动窗口值为k;
- 维护单向队列保存下标值,左右两个下标,[左大,右下],左边的下标值代表的数值最大,右边最小,使队列中的元素从大到小。
当当前值大于单向队列中的队尾值时,删除队尾值,使单向队列的元素值从大到小顺序保存,如果左右下标的区间值超过了滑动窗口值,则更新左边界。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int length = nums.length;
//队列保存的是下标值,下标值的区间来维护滑动窗口的大小长度
Deque<Integer> queue = new LinkedList<>();
//初始化滑动窗口
for(int i = 0;i<k;i++){
//保证滑动窗口的下标[左大,右小]。当前值大于队尾元素 则更新最大值
while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]){
queue.pollLast();
}
//向队尾添加元素
queue.addLast(i);
}
int[] res = new int[length - k + 1];
res[0] = nums[queue.peekFirst()];
for(int i = k;i<length;i++){
//如果当前值大于队尾元素,则直接出队,
while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]){
queue.pollLast();
}
//将当前下标存入队尾
queue.addLast(i);
//维护滑动窗口的大小
while(queue.peekFirst() <= i - k){
queue.pollFirst();
}
res[i-k+1] = nums[queue.peekFirst()];
}
return res;
}
}
大顶堆
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//大顶堆
int n = nums.length;
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] pair1, int[] pair2){
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{
nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{
nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
}
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hequnwang10/article/details/124341517
边栏推荐
- 01-初识sketch-sketch优势
- El date picker limits the selection range from the current time to two months ago
- Node template engine (EJS, art template)
- [related to zhengheyuan cutting tools]
- Shell-cut命令的使用
- C语言程序设计之函数的构造
- Advantages and disadvantages of several note taking software
- 常用SQL语句总结
- Double pointer advanced -- leetcode title -- container with the most water
- JS to find the character that appears three times in the string
猜你喜欢
[WPF binding 3] listview basic binding and data template binding
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
C# Task. Delay and thread The difference between sleep
Tdan over half
Solution architect's small bag - 5 types of architecture diagrams
ASP. Net core dependency injection service life cycle
ASP. Net core JWT certification
嵌入式系统中,FLASH中的程序代码必须搬到RAM中运行吗?
[difference between Oracle and MySQL]
1-1 NodeJS
随机推荐
QT modification UI does not take effect
Baidu Map Case - modify map style
How to use the input table one-way service to send (occupy less) picture files (body transmission)? FileReader built-in object involved
[registration] tf54: engineer growth map and excellent R & D organization building
stm32入门开发板选野火还是正点原子呢?
Use of todesk remote control software
Excel quickly and automatically fills the contents of a row on a blank cell
. net type transfer
Shell-sort命令的使用
JS failed to change all variables and changed to the return method. Finally, the problem was solved
開期貨,開戶雲安全還是相信期貨公司的軟件?
Qt 修改UI没有生效
ASP. Net core reads the configuration file in the class library project
El cascade and El select click elsewhere to make the drop-down box disappear
Node template engine (EJS, art template)
Wiper component encapsulation
uni-app黑马优购项目学习记录(下)
If you start from zero according to the frame
基于51单片机红外无线通讯仿真
HCIP第五次实验