单调栈思想与方法总结

单调栈

单调栈的精粹感觉不仅是单调的处理，更是栈里面大小的处理。很多的时候，题目里面都有大小的反馈，我们一般是维护单调栈，根据其中的规律，去进行大小的处理。而后得出答案。

单调栈最基本的运用

我们通过单调栈，去维持一个递增或者递减的情况。当然我们最重要的不是求其中递增递减的情况，反而是我们前面的情况，因为我们并不会直接对本点进行处理，反而是对之前的点进行处理。

 
stack<pair<int,int>>stk ; 
int n ; cin >> n ;  
vector<int>ans(n+1) ; 
for(int i =1 ; i<= n ; i++){
   int x; cin >> x ; 
   while(!stk.empty() && stk.top().x < x){
      ans[stk.top().y] = i ; 
      stk.pop() ; 
   }
   stk.push({x,i}) ; 
} 

for(int i = 1;  i<= n ; i++)cout << ans[i] << ' '  ;

懂的了这一点，我们就需要从题目中抽象出情况，接下来是我遇到的两种情况。

最大的矩形纸片

我们需要对我们的函数，维持一种递增似的形状，若是发生了递减情况，则是需要进行运算，这我们就可以使用单调栈，利用单调栈的性质我们进行计算和处理。


stack<pair<i64, i64>>stk ; 
 vector<i64>a(n+2) ; 
 for(int i = 1;  i<= n ; i++ )cin >> a[i] ; 
 for(int i = 1; i <= n + 1  ; i++){
    i64 sz = 0 ;  
    while(!stk.empty() && stk.top().x > a[i]){
       sz = sz + stk.top().y ; //sz + 1非常巧妙，完美把我之前计算的问题解决了
       ans = max(ans, sz * stk.top().x) ; 
       stk.pop() ;  
    }//维护一个递减的
    stk.push({a[i],sz+ 1}) ; 
 }
 cout << ans << '\n' ;

玉蟾宫

这一题主要是我们需要对其中的相等高度进行处理，所以我们变成维持递增，如果小我们就计算。这边sz的运用也很值得称道。因为这题宽度是可以继承的，所以我们进行如此。

有些题目是进行二维的形式。但是我们抽象完了以后，同样如果只需要对维持峰形的计算，那么我们同样可以进行此刻。单调栈运用了前面的数据，很多时间复杂度是 $ O(n^2) $


vector<vector<int>>a(n+1 ,vector<int>(m+2 )),mp(n+1 ,vector<int>(m+2));
for(int i =1 ;i<= n ; i++){
   for(int j = 1 ; j<= m ; j++){
   char x ; cin>> x ; 
   if(x =='R')a[i][j] = 0 ; 
   else a[i][j] = 1 ; 
   }
}
for(int j = 1 ; j<= m ; j++){
   for(int i = 1;  i<= n ; i++){
      mp[i][j] = mp[i-1][j] + 1 ; 
      if(!a[i][j])mp[i][j] = 0 ; 
   }
}
i64 ans = 0 ; 
for(int i = 1; i<= n ; i++){
   stack<pair<int,int>>stk ; 
   for(int j = 1 ; j<= m + 1 ; j++){
      i64 sz = 0 ; 
      while(!stk.empty() && stk.top().x > mp[i][j]){
         sz += stk.top().y ; 
         ans = max(ans , sz * stk.top().x ) ;             
         stk.pop() ;  
      }
      stk.push({mp[i][j] , sz+1}) ; 
   }
}
cout << ans * 3 << '\n' ;

[COCI 2010/2011 #3] DIFERENCIJA

此等类型，要求我们去求 $$\sum_{i=1}^{n} \sum_{j=i}^{n} (\max_{i\le k\le j} a_k)$$

这样子的题目，其实如果从左边往右边扩展，我们会发现是比较难得，我们完全不知道究竟要到哪里才结束，时间复杂度可能很高。但是正难则反。我们可以倒过来，去思考到哪里才不是他的最大值，这样是就把他的想法去取反了。

这样子，我们就可以发现，题目我们只需要对每一个收录进去的去处理，看看有没有比他更大的，若是有比他更大的，就结束了的情况。而我们又要对每一个进行相乘，我们就可以自然的想到在每一次栈的处理中进行运算。对他的位置进行计算。

当然，又因为我们是对每一个有可能是栈顶的进行处理，所以很有可能处理多了，所以我们就要对不是栈顶的机械能撤回操作，即为


vector<i64>a(n+2) ; 
 for(int i =1 ; i<= n ; i++)cin >> a[i] ; 
 stack<int>stk ; 
 i64 sum = 0 ; 
 i64 ans = 0 ; 
 stk.push(0) ; 
 for(int i = 1; i <= n ; i++){
    while(stk.size() > 1 && a[stk.top()] < a[i]){//既然我们是不断衍生，左边到右边不好统计，所以就尝试从右边到左边
       int x = stk.top() ; 
       stk.pop() ; 
       sum -= (x - stk.top()) * a[x] ; 
    }
    sum+=((i - stk.top()) * a[i]) ; 
    ans+= sum ; 
    stk.push(i) ;  
 }

#### [「ROI 2025 Day1」奥林匹克楼梯](https://www.luogu.com.cn/problem/P12501)

我们思考这一题，其实和玉蟾宫处理方式很像，这边就不重复了，不过这里面，和玉蟾宫不同的是，一个弹出以后就不会贡献，一个仅仅只是削平了，高的加低的，高的变成了底的。我们发现仍然可以贡献，此刻我们就可以使用一个sum，进行维护，一旦高了，我们就对sum调整。这样子我们就完成了计算的情况。

 for(int j = 1 ; j<= m ; j++){
   stack<PII>stk ;
   i64 sum = 0  ;  
   for(int i = 1; i<= n + 1 ; i++){
      i64 sz = 0 ;
      while(!stk.empty() && stk.top().x > mp[i][j]){
         sum -=(stk.top().x - mp[i][j]) * stk.top().y ;
         sz+= stk.top().y ; 
         stk.pop() ;  
       }
       sum += mp[i][j] ;  
       ans = max(ans , sum) ; 
       stk.push({mp[i][j] , sz + 1 }) ; 
   }
   // cout << sum <<  '\n' ; 
   while(!stk.empty())stk.pop() ; 
}
cout << ans << '\n' ;

整理思维

哨兵节点

为了防止最后有数据并没有计算的情况，有时候我们会在边界塞入几个边界点，使里面的数据进行全部强制更新。最后只需要弹出即可。

盖棺定论

向前计算，主要是计算这作为节点极值所贡献的答案，特征是，当这个栈弹出的时候，就已经结束了。我们可以立即计算他作为极值所贡献的答案，注意的是，每一个元素只会被弹出一次，当弹出的时候，他作为答案的可能性我们将其计算。所以就称为盖棺定论。

操作：

弹出元素
确定边界
计算贡献

典型问题

下一个更大元素、柱状图中最大的矩形、玉蟾宫。这类问题的特点是，每个元素的贡献在出栈时就能完全确定，之后不会再改变。

向后累计

向后累计，主要是进行解决此节点作为极值所贡献的答案，两者根本不同在于，一个是这里就结束了，一个是可能后面仍然有可能存在，所以我们需要继续维护。当我们发现他影响结束以后，我们再统一进行处理。

维护一个动态的累计贡献值sum，当新元素入栈可能会破坏单调性的同时，我们把过去的贡献值给删除，并且把新的贡献值加上。我们以此计算完以遍历位置为结尾所有满足可能性的贡献之和。

操作：

弹出并撤销
计算累加
更新答案

经典问题

所有子数组极值之差的和这类问题的特点是，需要动态地知道以每个位置为结尾的所有区间的极值信息。

下标与值的情况

我们的单调栈有时候存的是下标，有时候存的是数量，那么什么时候用数量，什么时候用下标呢？

这种情况我们就需要考虑，哪一种实现方式简便，传下标的优势就是，我们可以单独将下标进行处理，将问题拆分。传值的优势则是，我们减少了代码量，使逻辑更加清晰，但是在需要复杂求值的情况，此时我们就最好把计算后的结果取出，方便我们后面计算。

小苯的序列分段

例如此题，答案需要我们进行计数，并且单调栈处理以后我们仍需继续处理，所以我们更优的解法就是，我们将单调栈的处理结果保留下来，然后后面在进行统一的计算，将复杂的计数+单调栈分成了计数与单调栈分别处理，简化了难度，并且清晰了逻辑

int n , m ;cin >> n >> m ;
vector<int>a(n+1) , mp(n+1) ; 
for(int i = 1; i<= n ; i++)cin >> a[i] , mp[a[i]] = i  ; 
stack<int>stk ; 
vector<int>R(n+1 , n+1) , L(n+1 ) ;
for(int i = n ; i> 0 ; i--){
   while(!stk.empty() && a[stk.top()] < a[i]){
      stk.pop();
   }
   if(!stk.empty()){
      R[i] = stk.top() ; 
   }
   stk.push(i) ; 
} 

while(!stk.empty())stk.pop() ; 

for(int i = 1 ; i<= n ; i++){
   while(!stk.empty() && a[stk.top()] < a[i]){
      stk.pop();
   }
   if(!stk.empty()){
      L[i] = stk.top() ; 
   }
   stk.push(i) ; 
}
vector<int>b(m+1) ; 
for(int i = 1 ; i<= m ; i++)cin >> b[i] , b[i] = mp[b[i]] ;
i64 ans = 1 ; 
if(L[b[1]] > 0 || R[b[m]] <= n ){
   ans = 0 ; 
}
for(int i = 1;  i< m ; i++){
   int r = min(R[b[i]] , b[i+1] ) - 1  ,l = max(b[i] , L[b[i+1]]) ; 
   ans *= max(0 , r - l + 1 ) ;
   ans %= MOD ; 
}
cout << ans << '\n' ;

小苯的数组计数

这一题，我们不仅需要在出现一个 > 的情况盖棺定论，而且还要对里面的数值进行贡献计算。我们同样也是可以混用的，只不过我们把贡献和盖棺定论进行了融合，在贡献的时候我们贡献，在盖棺定论的时候，我们进行数据的结束。算法模板只是一个模板，里面具体有什么东西还给我们来定，思维方式只是为我们找到一个最好的切入点，而一个算法的灵魂在于我们的算法思维。


int n ; cin >> n ; 
vector<int>a(n+2) ; 
for(int i =1 ; i<= n ; i++)cin >> a[i] ;
i64 ans = 0 ;
stack<int>stk ; 
for(int i = 1 ; i<= n + 1  ; i++){
   while(!stk.empty() && a[stk.top()] < a[i] ){
     // cout << stk.top() << ' ' << i <<  ' ' << ans << '\n' ; 
      if(i - stk.top()+ 1 >= 3 )ans++ ;
      stk.pop() ;  
   }
   if(!stk.empty() && a[stk.top()] == a[i])stk.pop() ;  
   else if(!stk.empty()&&  i - stk.top() + 1 >= 3) ans++ ; 
   // cout << stk.size() << ' ' << ans << '\n' ; 
   stk.push(i) ; 
}
cout << ans << '\n' ;