Description
给出数组\(nums[]\)，滑动窗口大小\(k\)，求每个滑动窗口的最大值
Constraints
- \(nums[]\)长度不超过\(10^5\)
- \(nums[i]\)可以是负数
Solution
单调队列即可，维护单调最大值
Code
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if(nums.size() <= k) return {*std::max_element(nums.begin(), nums.end())};
deque<tuple<int, int>> monoq;
vector<int> ans;
for(int i = 0; i < nums.size(); ++i) {
while(!monoq.empty() && get<0>(monoq.front()) < i - k + 1) monoq.pop_front();
while(!monoq.empty() && get<1>(monoq.back()) <= nums[i]) monoq.pop_back();
monoq.emplace_back(make_tuple(i, nums[i]));
if(i >= k-1) ans.emplace_back(get<1>(monoq.front()));
}
return ans;
}
};