给定一个序列 a a a ，对于 a a a 中的每个数找到在他左（右）边，最近的比他大（小）的数是什么。
例：对于 a a a 中的每个数找到他左边最近的比他小的数是什么，没有输出 -1
5 3 4 2 7 5 ans = -1 3 -1 2 2
栈内一开始放入负无穷，对每个 a [ i ] a[i] a[i] 和栈顶元素判断就行，如果 a [ i ] a[i] a[i] 更小，那么栈顶元素就不是比 $a[i] $ 小的元素，不断弹栈，直到不能弹完为止。
解释单调栈为什么是单调的。
指针遍历到
i
i
i ,有下标
x
<
y
x 如果要求右边，就从n到1循环。 求最小，就是
a
[
i
]
<
=
栈顶元素
a[i] <= 栈顶元素
a[i]<=栈顶元素 ，哨兵置 -0x3f3f3f3f。 还有一种记忆方法： y总是用栈空不空判断的 建议以后都写 加哨兵的写法，不用判断边界 总结：单调栈和单调队列都可以叫 双端队列 ， 单调栈可以存值存下标。单调队列为了判断队头何时出队，存数组下标。 对于每一行，先预处理出up[]来，然后做n遍单调栈。 单调栈综合应用。 主要还是思维。 注意求 R时，单调栈中的指针是比i指针靠右的，就像求L时，单调栈中的指针比i指针靠左一样！ 和求最大矩形面积类似，但是我搞不懂怎么算的方案数（真看不懂） 排序后发现，当前数会被后边的数删掉，并且当前数的存在不影响后边的数。 对于
i
i
i 找
1
≤
a
[
j
]
−
a
[
i
]
≤
k
1 le a[j]-a[i] le k
1≤a[j]−a[i]≤k 的
j
j
j , 可以找最小的
a
[
j
]
>
a
[
i
]
+
k
a[j] > a[i]+k
a[j]>a[i]+k , 判断
a
[
j
−
1
]
−
a
[
i
]
a[j-1] - a[i]
a[j−1]−a[i] 是否大于1。 法一：upper_bound。 法二：双指针。 证明正确性： 一般双指针都是找4个指针，然后找一个矛盾。 枚举到
i
i
i ,有
j
j
j 满足
a
[
j
]
>
a
[
i
]
+
k
,
a
[
j
]
最小
a[j] > a[i] +k,a[j]最小
a[j]>a[i]+k,a[j]最小 。
i
i
i 向右移动到了
i
′
i'
i′ ,假设有
j
′
<
j
j' < j
j′ 发现
a
[
j
−
1
]
−
a
[
i
]
≤
k
a[j-1]-a[i] le k
a[j−1]−a[i]≤k 有，
a
[
j
−
1
]
−
a
[
i
′
]
≤
k
a[j-1]-a[i'] le k
a[j−1]−a[i′]≤k , 所以
i
′
i'
i′ 对应的
J
J
J 最小也是
j
j
j 不是
j
′
j'
j′ ,矛盾，说明，
i
i
i 向右过程中 ，
j
j
j 也是单调向右的。stk[++tt] = -0x3f3f3f3f;
fo(i,1,n){
// 一直有-无穷
while(a[i] <= stk[tt]) // 如果是<=,栈内元素会是严格单调增的
tt--;
if(stk[tt] == -0x3f3f3f3f)
cout<<"-1 ";
else
cout<int a[N],stk[N],tt;
void solve(){
cin>>n;
fo(i,1,n){
cin>>a[i];
}
stk[++tt] = -0x3f3f3f3f;
fo(i,1,n){
// 一直有-无穷
while(a[i] <= stk[tt])
tt--;
if(stk[tt] == -0x3f3f3f3f)
cout<<"-1 ";
else
cout<int a[N],stk[N],tt;
void solve(){
cin>>n;
fo(i,1,n){
cin>>a[i];
}
fo(i,1,n){
// 一直有-无穷
while(tt && a[i] <= stk[tt])
tt--;
if(tt)
cout<
131. 直方图中最大的矩形
ll pre[N],suf[N];
void solve(){
while(cin>>n,n){
tt=0;
ll ans=0;
fo(i,1,n)cin>>a[i];
h[0] = h[n+1] = -1;
stk[0] = 0;
fo(i,1,n){
while(a[i] <= a[stk[tt]]){
tt --;
}
pre[i] = stk[tt];
stk[++tt] = i;
}
tt=0;
stk[0] = n+1;
for(int i=n;i>=1;i--){
while(a[i] <= a[stk[tt]]){
tt -- ;
}
suf[i]=stk[tt];
stk[++tt] = i;
}
for(int i=1;i<=n;i++){
cout<N遍直方图中的最大矩形，注意单调栈写带哨兵的int n,m;
char a[1100][1100];
int up[1100][1100];
int stk[1100],tt;
int ans;
void work(int x[1100]){
int l[1100],r[1100];
// 左边第一个比他小的数,带哨兵的
x[0] = x[m+1] = -1;
stk[++tt] = 0;
for(int i=1;i<=m;i++){
while(x[i] <= x[stk[tt]])
tt--;
l[i] = stk[tt]; // 下标
stk[++tt]=i;
}
tt = 0;
stk[++tt] = m+1;
for(int i=m;i>=1;i--){
while(x[i] <= x[stk[tt]])
tt--;
r[i] = stk[tt];
stk[++tt]=i;
}
for(int i=1;i<=m;i++){
ans = max(ans,(r[i]-1-(l[i]+1)+1) * x[i]);
}
}
void solve(){
cin>>n>>m;
fo(i,1,n)fo(j,1,m)cin>>a[i][j];
fo(i,1,n){
fo(j,1,m){
if(a[i][j] == 'R') up[i][j] = 0;
else{
up[i][j] = up[i-1][j]+1;
}
}
}
// 做n遍直方图中的最大矩形。
fo(i,1,n){
work(up[i]);
}
cout<
3780. 构造数组
const int N=1e6+10,M=1e9+7;
ll n,a[N],l[N],r[N];
ll ans[N];
int stk[N],tt;
void solve(){
cin>>n;
fo(i,1,n)cin>>a[i];
// 求每个元素第一个比他小的元素
tt = 0;
a[0] = -1;
stk[++tt] = 0;
for(int i=1;i<=n;i++){
while(a[i] <= a[stk[tt]])
tt--;
int left = stk[tt];
l[i] = l[left] + (ll)(i-left)*a[i];
stk[++tt] = i;
}
a[n+1] = -1;
tt = 0;
stk[0] = n+1;
for(int i=n;i>=1;i--){
while(a[i] <= a[stk[tt]])
tt--;
int left = stk[tt];
// cout<
P1950 长方形
学会了另一种计算图形中长方形的方法，确定两条边，组合数学乘法原理就行。typedef long long ll;
int n,m,a[1100][1100];
int l[1100],r[1100]; // l表示左边第一个不大于 ， r表示右边第一个小于 ans = (i-l)*(r-i)*h
int up[1100][1100];
int stk[N],tt;
ll ans;
void work(int x[]){
tt = 0;
x[0] = -1;
stk[++tt] = 0;
fo(j,1,m){
while(x[j] < x[stk[tt]])
tt--;
l[j] = stk[tt];
stk[++tt] = j;
}
tt = 0;
x[m+1] = -1;
stk[++tt] = m+1;
for(int j=m;j>=1;j--){
while(x[j] <= x[stk[tt]])
tt--;
r[j] = stk[tt];
stk[++tt] = j;
}
// fo(i,1,m)cout<
双指针
4483. 格斗场
int n,k,a[N];
void solve(){
cin>>n>>k;
fo(i,1,n)cin>>a[i];
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<=n;i++){
int j = upper_bound(a+1,a+n+1,a[i]+k)-a;
if(a[j-1] - a[i] >=1) ans ++;
}
cout<原来双指针while中 j 的限制可以绝对 i和j哪个是尾指针，哪个是头指针int n,k,a[N];
void solve(){
cin>>n>>k;
fo(i,1,n)cin>>a[i];
sort(a+1,a+n+1);
// 42 53 54 55 101 101 102
int ans=0;
for(int i=1,j=1;i<=n;i++){
while(j<=n && a[j] - a[i] <=k){
j++;
}
if(a[j-1] - a[i] >=1) ans ++;
}
cout<
