给你一个整数数组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] 1041 k nums.length思路1、创建一个大小为k的大顶堆,用pairint,int构建元素第一个是数组的值第二个是数组的下标。创建两个指针left0、rightk-1把指针中间的数字先加入大顶堆创建临时的vector用于存放最大值。2、从堆顶拿一个元素判断这个元素的下标是否是在left和right之间的是则将元素放入答案中否则将这个堆顶元素删除继续获取堆顶元素循环判断。3、循环结束条件right要大于数组的下标时结束循环。class Solution { public: vectorint maxSlidingWindow(vectorint nums, int k) { vectorint _ans; int nnums.size(); if(nk) return _ans; priority_queuepairint,int max_head; for(int i0;ik;i){ max_head.push({nums[i],i}); } int left0,rightk-1; while(1){ pairint,int emitmax_head.top(); while(emit.secondleft){ max_head.pop(); emitmax_head.top(); } _ans.push_back(emit.first); left; right; if(rightn) break; max_head.push({nums[right],right}); } return _ans; } };//priority_queue优先队列 #include queue // priority_queue 在 queue 头文件中 //创建大顶堆 std::priority_queuepairint,int pri_queue; std::priority_queue int, // 元素类型 std::vectorint, // 底层容器必须是 vector 或 deque std::greaterint // 比较器小顶堆 min_heap; pairint,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::vectorintstd::dequeint内存布局连续内存所有元素存储在一块连续的空间中分段内存由多个固定大小的内存块组成缓存友好性✅ 极高遍历/堆操作时 CPU 缓存命中率高❌ 较差元素分散在不同内存块缓存命中率低内存扩容容量不足时会重新分配并拷贝/移动所有元素可能导致迭代器失效新增块时不会移动已有元素迭代器不会失效内存开销较小仅有一个动态数组的开销较大需要额外维护指向各个块的指针数组尾部插入性能均摊 O(1)但扩容时有峰值开销均摊 O(1)无峰值开销适用场景优先推荐性能更好当需要避免扩容时移动开销巨大的元素类型时可选推荐一个零声教育学习教程个人觉得老师讲得不错分享给大家[LinuxNginxZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerTCP/IP协程DPDK等技术内容点击立即学习:链接