单调栈

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

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

  1. 【算法】
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;	// 把当前值放在合适地方
}
  1. 【应用一】
    直方图中最大的矩形
    算法思想:
    ① 以每一个矩形的高为标准,找出左右两边第一个小于此矩形高的矩形,枚举所有
    的矩形,找出最大面积。
    ② 利用单调栈,进行预处理将每个矩形左右两边的第一个小于此矩形高的矩形。
#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;
}
  1. 【应用二】
    城市游戏
    算法思想:
    联想【应用一】,统计每一行向上的高度,再利用应用一单调栈的解题方法,遍历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;
}
作者:sxy666666原文地址:https://www.cnblogs.com/sxy666666/p/17085933.html

%s 个评论

要回复文章请先登录注册