单调栈和单调队列（单调栈）

顾名思义单调栈就是具有单调性的栈

常见模型：找出每个数左边离它最近的比它大/小的数

【算法】 int stk[N],tt = 0; // 栈中存数据 for (int i = 1; i <= n; i ++){ int x; cin >> x; while (tt && stk[tt] >= x) tt -- ; // 左边比它小的数 stk[ ++ tt] = i; // 把当前值放在合适地方

} 【应用一】

直方图中最大的矩形

算法思想:

① 以每一个矩形的高为标准    
    
    
 ，找出左右两边第一个小于此矩形高的矩形 


     


     


     ，枚举所有

的矩形

 




 




 




，找出最大面积
    
    
    
。

② 利用单调栈   

   

   

，进行预处理将每个矩形左右两边的第一个小于此矩形高的矩形     


     


     


 。 #include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010; int n;// h: 高度 q: 单调栈->记录h的下标 l: 左边符合条件距离 r: 右边符合条件距离 int h[N],q[N],l[N],r[N]; void solve(){ while (scanf("%d", &n),n){ for (int i = 1; i <= n; i ++) scanf("%d",&h[i]); h[0] = h[n + 1] = -1; // 预处理要边界条件 // 找出左边第一个高度小于当前 int tt = -1; q[++ tt] = 0; // 下标 0 for (int i = 1; i <= n; i ++){ while (h[q[tt]] >= h[i]) tt --;//维护好单调栈: 找到栈中第一个小于当前值的数据 l[i] = i - q[tt]; // 记录i左边第一符合条4 件的数据距离 q[++ tt] = i; // 当前值下标入栈 } // 同理求右边 tt = -1; q[++ tt] = n + 1; for (int i = n; i >= 1; i --){ while (h[q[tt]] >= h[i]) tt --; r[i] = q[tt] - i; q[++ tt] = i; } LL res = 0; for (int i = 1; i <= n; i ++) res = max(res, (LL)h[i] * (l[i] + r[i] - 1));// - 1是因为计算左右两边就多加一个h[i] printf("%lld\n", res); } } int main(){ solve(); return 0

; } 【应用二】

城市游戏

算法思想: 联想【应用一】  

     

     

     ，统计每一行向上的高度


  




  




  



，再利用应用一单调栈的解题方法  


  


  


，遍历n行   
     
     
    ，求出最优解 




 




 




 。 #include <iostream> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; typedef pair<int,int> PII; const int N = 1010; int n,m,res; int h[N],q[N],l[N],r[N]; // 这里就是【应用一】一行的解题方法 void solve(){ for (int i = 0; i <= m + 1; i ++)q[i] = 0; h[0] = h[m + 1] = -1; int tt = -1; q[++ tt] = 0; for (int i = 1; i <= m; i ++){ while (h[q[tt]] >= h[i]) tt --; l[i] = i - q[tt]; q[++ tt] = i; } tt = -1; q[++ tt] = m + 1; for (int i = m; i >= 1; i --){ while (h[q[tt]] >= h[i]) tt --; r[i] = q[tt] - i; q[++ tt] = i; } for (int i = 1; i <= m; i ++) res = max(res, h[i] * (l[i] + r[i] - 1)); } int main(){ cin >> n >> m; for (int i = 0; i < n; i ++){ for (int j = 1; j <= m; j ++){ char c; cin >> c; // 这里建议用cin 自动省略空格回车 if (c == R) h[j] = 0; // 遇R高度就变0 else h[j] += 1; } solve(); } printf("%d\n", res * 3); return 0; }