登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.3 单调栈与单调队列 › 单调栈与单调队列 / 搜索
JSON MD

2.3 单调栈与单调队列

单调队列 monotonic_queue
18 行
CPP JSON
【单调队列——滑动窗口最大值】 ▪ maxSlidingWindow(nums, k) — 返回每个长度为 k 的滑动窗口的最大值: ① 维护双端队列 dq,存储候选最大值的下标(对应值从大到小单调递减) ② 队首过期(下标 < i-k+1)则 pop_front ③ 队尾值 ≤ 新值则 pop_back(维护单调性) ④ 将新下标 push_back,i≥k-1 时输出 nums[dq.front()] 每个元素入队/出队各一次,时间复杂度 O(N)。适用于滑动窗口最值、DP 单调队列优化。
C++ 18 行 CPP
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> res;
    deque<int> dq;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }
        while (!dq.empty() && nums[i] >= nums[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
        if (i >= k - 1) {
            res.push_back(nums[dq.front()]);
        }
    }
    return res;
}
单调栈类 monotonic_stack
14 行
CPP JSON
【单调栈——Next Greater Element】 ▪ nextGreaterElement(nums) — 返回每个元素右侧第一个比它大的元素值(不存在为 -1): 遍历数组,维护栈内元素对应值单调递减。当新元素 nums[i] > 栈顶对应值时,栈顶出栈并记录答案 res[栈顶]=nums[i]。最终将 i 入栈。 每个元素入栈出栈各一次,时间复杂度 O(N)。可改造成左侧更大、更小等变体。适用于 Next Greater Element、柱状图最大矩形、接雨水、股票价格跨度等。
C++ 14 行 CPP
// 单调栈:寻找每个元素右侧第一个比它大的元素
vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, -1);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[i] > nums[st.top()]) {
            res[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}
已复制