[算法基础学习] 单调栈和单调队列

注意！单调栈和单调队列与 for 一起遍历数组时，时间复杂度是o(n)，根据摊还分析。

单调栈

应用举例：求某个点左侧或右侧第一个比它大的点的位置

核心思想：入栈时与栈顶进行比较，或栈顶元素更差，就删除它。

用数组实现的单调栈，可以在里面进行二分。

单调队列

一般不会从队尾进元素。

经常把下标作为单调队列里的元素，而不是元素值。

例题与代码

#include <iostream>
#include <stack>
#define ll long long
using namespace std;

const int N = 7e5+5;
int a[N];
stack<int> s1;
stack<int> s2;
int res1[N];
int res2[N];

int main()
{
  // 请在此输入您的代码
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n;
  cin >> n;
  for(int i = 1 ; i <= n ; i++){
    cin >> a[i];
  }
  for(int i = 1 ; i <= n ; i++){
    int x=-1;
    while(!s1.empty()){
      x = s1.top();
      //s1.pop();
      if(a[x]>a[i]){
        s1.push(i);
        break;
      }
      else {
        s1.pop();
      }
    }
    if(s1.empty()){
      res1[i]=-1;
      s1.push(i);
    }
    else{
      res1[i]=x;
    }
  }
  for(int i = n ; i>= 1 ; i--){
    int x = -1;
    while(!s2.empty()){
      x = s2.top();
      if(a[x]>a[i]){
        s2.push(i);
        break;
      }
      else {
        s2.pop();
      }
    }
    if(s2.empty()){
      res2[i]=-1;
      s2.push(i);
    }
    else{
      res2[i]=x;
    }
  }
  for(int i = 1 ; i <= n ; i++){
    cout<< res1[i] << ' ';
  }
  cout << '\n';
  for(int i = 1 ; i <= n ; i++){
    cout << res2[i] <<' ';
  }

  return 0;
}

这是用数组实现的代码