当前位置:网站首页>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
边栏推荐
猜你喜欢
双闭环直流调速系统matlab/simulink仿真
Collection of common SQL statements
For the space occupation of the software, please refer to the installation directory
Compare the performance of query based on the number of paging data that meet the query conditions
PC电脑使用无线网卡连接上手机热点,为什么不能上网
练习:求偶数和、阈值分割和求差( list 对象的两个基础小题)
MySQL installation
[ES6] promise related (event loop, macro / micro task, promise, await / await)
01-初识sketch-sketch优势
Use of todesk remote control software
随机推荐
RPC核心概念理解
PC电脑使用无线网卡连接上手机热点,为什么不能上网
[WPF binding 3] listview basic binding and data template binding
flink 学习(十二)Allowed Lateness和 Side Output
Entity Framework core captures database changes
Self use learning notes - connectingstring configuration
Node template engine (EJS, art template)
Double pointer advanced -- leetcode title -- container with the most water
The system cannot be started after AHCI is enabled
stm32入门开发板选野火还是正点原子呢?
[difference between Oracle and MySQL]
Input file upload
Some problems encountered in recent programming 2021 / 9 / 8
ClickHouse-表引擎
JS failed to change all variables and changed to the return method. Finally, the problem was solved
Promise (II)
Devexpress GridView add select all columns
Collection of common SQL statements
[二叉数] 二叉树的最大深度+N叉树的最大深度
Future 用法详解