37 lines
1.1 KiB
C++
37 lines
1.1 KiB
C++
#include "s0239_sliding_window_maximum.hpp"
|
|
#include <utility>
|
|
|
|
// 优先级队列实现，每次操作的时间复杂度是 O(log(n)) ，因此总的时间复杂度是 O(n*log(n))
|
|
// 空间复杂度是 O(n)
|
|
vector<int> S0239::maxSlidingWindow(vector<int>& nums, int k) {
|
|
int len = nums.size();
|
|
if (len < 1 || k < 1) {
|
|
return {};
|
|
}
|
|
vector<int> result;
|
|
// 初始化优先级队列
|
|
priority_queue<pair<int, int>> q;
|
|
for (int i{0}; i < len && i < k; ++i) {
|
|
q.push(make_pair(nums[i], i));
|
|
}
|
|
if (k >= len) {
|
|
return {q.top().first};
|
|
} else {
|
|
result.push_back(q.top().first);
|
|
}
|
|
// 开始迭代
|
|
for (int i{1}; i + k - 1 < len; ++i) {
|
|
// 本轮迭代中滑动窗口的范围是 [i...i+k-1]
|
|
// 先把右边的元素放入队列
|
|
q.push(make_pair(nums[i + k - 1], i + k - 1));
|
|
// 确保队首元素在滑动窗口内
|
|
// 如果不在滑动窗口内，则弹出
|
|
while (q.top().second < i) {
|
|
q.pop();
|
|
}
|
|
// 现在队首元素就是滑动窗口内的最大值了
|
|
result.push_back(q.top().first);
|
|
}
|
|
return result;
|
|
}
|