当前位置:网站首页>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
边栏推荐
- Preliminary understanding of promse
- Simulation of infrared wireless communication based on 51 single chip microcomputer
- Allowed latency and side output
- 1-3 components and modules
- Freecodecamp ---- budget & category exercise
- ASP. Net core configuration options (Part 1)
- [related to zhengheyuan cutting tools]
- ClickHouse-SQL 操作
- [C] thoroughly understand the deep copy
- 開期貨,開戶雲安全還是相信期貨公司的軟件?
猜你喜欢
ASP. NET CORE3. 1. Solution to login failure after identity registers users
Signalr can actively send data from the server to the client
If you start from zero according to the frame
[difference between Oracle and MySQL]
Using quartz under. Net core - [1] quick start
Devexpress GridView add select all columns
Qt 修改UI没有生效
XTask与Kotlin Coroutine的使用对比
Use of todesk remote control software
. net type transfer
随机推荐
Collection of common SQL statements
MySQL installation
freeCodeCamp----prob_ Calculator exercise
How to change input into text
flink 学习(十二)Allowed Lateness和 Side Output
XTask与Kotlin Coroutine的使用对比
Devexpress GridView add select all columns
给 el-dialog 增加拖拽功能
In ancient Egypt and Greece, what base system was used in mathematics
stm32入门开发板选野火还是正点原子呢?
[C#] 彻底搞明白深拷贝
Use of shell cut command
1-3 components and modules
基于51单片机红外无线通讯仿真
Understanding of RPC core concepts
Using quartz under. Net core -- job attributes and exceptions of [4] jobs and triggers
古代埃及希腊,数学用的什么进制
Advantages and disadvantages of several note taking software
[registration] tf54: engineer growth map and excellent R & D organization building
为什么有些人说单片机简单,我学起来这么吃力?