题目描述

区分什么用单调队列 什么时候用单调栈
单调栈：求某一个数左边比它小或比它大的数（维护一个堆顶元素最小 和 堆顶元素最大 的栈）
单调队列：求某长度m的连续子序列(大小为m的滑动窗口)中，其最大值或最小值。或是求子序列和的最大最小值

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int main(){
    int n;
    cin >> n;
    stack<int> s;

    for(int i = 0 ; i < n; i++){
        int x ;
        cin >> x;
        //维护一个栈顶元素是最小的单调栈
        while(!s.empty() && x <= s.top()) s.pop();
        if(s.empty())
            cout << -1 << " ";
        else{
            cout << s.top() << " ";
        }
        s.push(x);

    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 10010;
int n;
int stk[N];
int main(){
    int tt = 0; // 栈顶指针
    cin >> n;
    for(int i = 0 ; i < n; i++){
        int x;
        cin >> x;
        // 如果当前栈顶元素大于等于x pop出栈这里用tt--
        while(tt && stk[tt] >= x) tt--;
        // 如果将比x大的元素pop出后tt还是大于0 那么此时栈顶元素就是第一个比它小的数
        if(tt) cout << stk[tt] << " ";
        // 否则输出-1
        else cout << -1 << " ";
        // 栈顶指针向前移动一位 再加入x值
        stk[++tt] = x;

    }

}