传送门
滑动窗口的最大值:给你一个整数数组 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]
提示:
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
if(nums.size() == k){
// 使用max_element()函数获取指定范围的最大值
auto submax = max_element(nums.begin(), nums.end());
res.push_back(*submax);
return res;
}
else{
for(int i = 0; i + (k - 1) < nums.size(); i++){
auto submax = max_element(nums.begin() + i, nums.begin() + i + k);
res.push_back(*submax);
}
return res;
}
}
};
通过遍历循环,不断获取每个窗口内的最大值。
时间复杂度:
O((n-k+1)*k) = O(nk),(n-k+1)为滑动窗口移动的次数。
空间复杂度:
O(n)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
// 创建一个优先队列,默认为最大堆
priority_queue<pair<int, int>> q;
// 先将前k个元素入堆
for (int i = 0; i < k; ++i) {
q.emplace(nums[i], i);
}
// 第一个窗口的最大元素
vector<int> ans = {q.top().first};
// 开始循环遍历求取每个窗口的最大值
for (int i = k; i < n; ++i) {
q.emplace(nums[i], i);
// 如果最大值不在当前窗口的范围内,则将其弹出,当前堆的最大值在窗口范围内
while (q.top().second <= i - k) {
q.pop();
}
ans.push_back(q.top().first);
}
return ans;
}
};
对于最大(小)值问题,我们可以使用优先队列帮我们维护一系列元素的最值。
因此,初始时我们先将前k个元素放进优先队列。然后开始向右循环遍历数组,当我们把一个新元素添加至优先队列时,此时堆顶的元素就是堆中最大的元素。但是这个最大元素可能并不在当前窗口中,那它必定在窗口的左侧。而我们往右滑动窗口时,此元素不能再出现在滑动窗口中,所以我们可以将不在当前窗口内的最大值从堆中移除。
时间复杂度:
O(nlogn)
空间复杂度:
O(n)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q;
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = {nums[q.front()]};
for (int i = k; i < n; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
while (q.front() <= i - k) {
q.pop_front();
}
ans.push_back(nums[q.front()]);
}
return ans;
}
};
个人感觉比较难想到,仅供参考,还是前面优先队列法比较通俗易懂。
时间复杂度:
O(n)
空间复杂度:
O(k)
优先队列是c++标准模板库中提供的一种基于优先级实现的队列。默认创建是一个最大堆(max heap),即队列中的最大元素总是位于队首。
1.头文件包含
#include <queue>
2.创建优先队列对象
std::priority_queue<int> pq; // 默认是最大堆
3.插入元素
pq.push(5);
pq.push(10);
pq.push(3);
4.访问堆顶元素
int maxElement = pq.top();
5.删除堆顶元素
pq.pop();
6.自定义比较函数
// 创建一个最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
7.遍历所有元素
while (!pq.empty()) {
int current = pq.top();
// 处理当前元素
pq.pop();
}
8.堆的大小
int heapSize = pq.size();
在 C++ 中,emplace 函数通常用于容器类,例如 std::vector、std::map、std::set 等。emplace 不同于 push_back 或 insert,它允许你在容器中构造元素,而不需要手动创建一个临时对象。
主要的优势是,emplace 直接在容器内部进行对象的构造,避免了临时对象的拷贝或移动操作,提高了效率。
以下是 std::vector 中的 emplace的示例:
#include <vector>
struct MyClass {
int a;
double b;
// 构造函数
MyClass(int x, double y) : a(x), b(y) {
// 可以在构造函数中加入其他初始化逻辑
}
};
int main() {
std::vector<MyClass> myVector;
// 使用 emplace_back 直接在容器内构造元素
myVector.emplace(42, 3.14);
myVector.emplace(10, 2.71);
return 0;
}
其他容器,如 std::map、std::set 也有对应的 emplace 函数,用法类似。这样的用法对于避免不必要的拷贝或移动操作,提高程序性能是有益的。
2024.1.12
欢迎前来讨论指正。