单调栈&单调队列

LQ_Q · 2025-03-23 11:20:24 · 算法·理论

单调栈

一.定义及概述

1.定义：

单调栈是一种内部元素具有单调性的栈。

1.概述：

利用出栈进栈的特性（入栈放最后，出栈出最后）来维护栈的单调性，利用该优化算法可以将 O(n^2) 的时间复杂的问题转化为 O(n) 。

1.适用场景

• 求某个区间（无长度限制）的最值。

  二.单调栈的适用问题特征

  1.目标为值的个数

• 在区间中某数的前(或后)的无长度限制区间存在多少个值比该数满足一定大小关系的的。

• 典型问题

  • 区间 （无长度限制的） 内满足一定数量关系 (如：大于，小于等) 的值的总个数

    三.单调栈的核心优化原理

    同过入栈出栈的方式维护单调栈，利用以下特征将复杂度 O(n^2) 转化为 O(n)

    1. 栈内单调性与不可逆性

• 入栈： 保证于栈顶满足规定的数量关系

• 出栈： 一直出栈直到满足入栈条件

• 避免重复遍历： 单向出入栈，跳过一定满足条件的值，以免重复比较。

  2.单向性

  每个元素最多入一次出一次，复杂度是 O(2n)->O(n)

  四.单调栈的基本模型

  int num[MAXN]; //数列的存储 
  stack<int>st; //单调栈用于存储下标 
  int ans=0; //答案记录 
  for(int i=1;i<=n;i++){
  //维护单调栈 
  while(!st.empty()&&num[st.top()] /*数量关系的反*/ num[i]){
      st.pop(); 
  }
  ans+=st.size(); //增加前 1~i-1 个数中于 num[i] 满足数量关系的高斯 
  st.push(a[i]); //入栈 
  } 

  五.典型例题分析

  P2866 [USACO06NOV] Bad Hair Day S

  问题描述

  给定一个数列，定义其中的每一个元素 i ，从 i+1 到第一个比 i 的值大或等于的元素所选中的区间中的元素个数和

  问题转化

  将问题转化为对于每一个元素 i 在 1~i-1 中所有满足给定数量关系的反及比元素 i 小的元素个数和

  单调栈策略

• 维护一个单调栈，栈内满足单调递减

• 核心操作 对于一个元素 i

  • 出栈： 栈顶小于等于 i
  • 入栈： 栈顶大于 i
    • 答案每次的增长值为：栈顶大于 i 时栈的长度

      代码实现

      #include<bits/stdc++.h>
      using namespace std;
      int n,t;
      long long ans;
      stack <int> a;
      int main(){
      cin>>n;
      for (int i=1; i<=n; i++) {
      cin>>t;
      while (!a.empty()&&a.top()<=t)  
      a.pop();
      ans+=a.size();
      a.push(t);
      }
      cout<<ans;
      return 0;
      }

      P8094 [USACO22JAN] Cow Frisbee S

      问题描述

      给定一个数列,给定每一个元素的值 h ,其中存在区间 [i,j] ,保证区间中，除左端点 i 和右端点 j 外所有的元素都小于 min(h [i],h[j]) 求所有满足该性质的区间的长度和

      问题转化

      固定右端点，求取所有满足条件的点

      单调栈策略

• 维护一个单调栈，栈内满足单调递减
• 核心操作：
  • 出栈： 栈顶小于等于 i
  • 入栈： 栈顶大于 i
• 答案统计： 所有被 出栈的元素 和 最后入栈时的前一个元素 都满足条件

  代码实现

#include<bits/stdc++.h>
using namespace std;
int n;
long long ans=0;
stack<int>st;
stack<int>sum;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        long long h;
        scanf("%lld",&h);
        while(!st.empty()&&h>=st.top()){
            ans+=(i-sum.top()+1);
            st.pop();
            sum.pop();
        }
        if(!st.empty()) ans+=(i-sum.top()+1);
        st.push(h);
        sum.push(i);
    }
    printf("%lld",ans);
}

单调队列

1.定义：

单调栈是一种内部元素具有单调性的队列。

1.概述：

利用队列双端的特性（可出头可出尾）来维护队列的单调性，利用该优化算法可以将 O(n^2) 的时间复杂的问题转化为 O(n) 。

1.适用场景

• 求某个区间（无长度限制）的最值。

• 1.目标为值的个数

• 在区间中某数的前(或后)的有长度限制区间存在多少个值与该数满足一定大小关系的。

  • 典型问题
  • 区间 （有长度限制） 内 最值 。

    三.单调栈的核心优化原理

    通过推出队头和压入或推出队尾的方式的方式维护单调队列，利用以下特征将复杂度 O(n^2) 转化为 O(n)

    1. 队内单调性与不可逆性

• 入队： 保证于队列尾满足规定的数量关系

• 出队（尾）： 一直出队直到满足入队条件

• 出队（首）： 推出所有不在区间范围内的数据

• 避免重复遍历： 单向出入队列，跳过一定满足条件的值，以免重复比较。

  2.单向性

  每个元素最多入一次出一次，复杂度是 O(2n)->O(n)

  代码实现