当前位置：首页 > news >正文

11 滑动窗口最大值

news 2026/7/25 20:03:03

给你一个整数数组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 731 [3 -1 -3] 5 3 6 731 3 [-1 -3 5] 3 6 751 3 -1 [-3 5 3] 6 751 3 -1 -3 [5 3 6] 761 3 -1 -3 5 [3 6 7]7

示例 2：

输入：nums = [1], k = 1输出：[1]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

思路

1、创建一个大小为k的大顶堆,用pair<int,int>构建元素，第一个是数组的值，第二个是数组的下标。创建两个指针，left=0、right=k-1，把指针中间的数字先加入大顶堆，创建临时的vector用于存放最大值。

2、从堆顶拿一个元素，判断这个元素的下标是否是在left和right之间的，是则将元素放入答案中，否则将这个堆顶元素删除，继续获取堆顶元素，循环判断。

3、循环结束条件right要大于数组的下标时，结束循环。

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> _ans; int n=nums.size(); if(n<k) return _ans; priority_queue<pair<int,int> > max_head; for(int i=0;i<k;i++){ max_head.push({nums[i],i}); } int left=0,right=k-1; while(1){ pair<int,int> emit=max_head.top(); while(emit.second<left){ max_head.pop(); emit=max_head.top(); } _ans.push_back(emit.first); left++; right++; if(right>=n) break; max_head.push({nums[right],right}); } return _ans; } };

//priority_queue（优先队列） #include <queue> // priority_queue 在 <queue> 头文件中 //创建大顶堆 std::priority_queue<pair<int,int>> pri_queue; std::priority_queue< int, // 元素类型 std::vector<int>, // 底层容器（必须是 vector 或 deque） std::greater<int> // 比较器：小顶堆 > min_heap; pair<int,int> emit; //访问pair的第一个元素：emit.first //访问pair的第二个元素：emit.second

基本函数

操作	函数	O(log n)	说明
插入元素	push(value)	O(log n)	插入元素到队列
删除堆顶	pop()	O(log n)	移除优先级最高的元素
访问堆顶	top()	O(1)	返回优先级最高的元素（不删除）
判空	empty()	O(1)	队列是否为空
大小	size()	O(1)	元素个数

底层容器选vector和deque有什么区别？

priority_queue支持vector和deque作为底层容器（也支持其他满足条件的序列容器，如list不支持随机访问，所以不行）。两者的区别主要体现在内存布局和性能特征上：

对比维度	`std::vector<int>`	`std::deque<int>`
内存布局	连续内存，所有元素存储在一块连续的空间中	分段内存，由多个固定大小的内存块组成
缓存友好性	✅ 极高，遍历/堆操作时 CPU 缓存命中率高	❌ 较差，元素分散在不同内存块，缓存命中率低
内存扩容	容量不足时会重新分配并拷贝/移动所有元素，可能导致迭代器失效	新增块时不会移动已有元素，迭代器不会失效
内存开销	较小，仅有一个动态数组的开销	较大，需要额外维护指向各个块的指针数组
尾部插入性能	均摊 O(1)，但扩容时有峰值开销	均摊 O(1)，无峰值开销
适用场景	优先推荐，性能更好	当需要避免扩容时移动开销巨大的元素类型时可选