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;
    }
};

LeetCode-239 Sliding Window Maximum