题解 | #最小活动范围# 单调队列

知识点

单调队列

思路

需要维护一个窗口的最小值，是单调队列的应用场景。单调队列板子题。

时间复杂度

对于每个值只加入队列一次、出队列一次，时间复杂度为线性的，时间复杂度

AC code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    vector<int> minSlidingWindow(vector<int>& nums, int k) {
        // 单调队列
        deque<int> q;
        int n = nums.size();
        vector<int> res;
        for (int i = 0; i < n; i++) {
            while (q.size() && i - q.front() + 1 > k) q.pop_front();
            while (q.size() && nums[q.back()] >= nums[i]) q.pop_back();
            q.push_back(i);
            if (i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};