单调栈

单调栈(模板)

给定一个序列 $a$ ，对于 $a$ 中的每个数找到在他左（右）边，最近的比他大（小）的数是什么。

例：对于 $a$ 中的每个数找到他左边最近的比他小的数是什么，没有输出 -1

       5
	   3 4 2 7 5
ans = -1 3 -1 2 2
1
2
3

栈内一开始放入负无穷，对每个 $a[i]$ 和栈顶元素判断就行，如果 $a[i]$ 更小，那么栈顶元素就不是比 $a[i] $ 小的元素，不断弹栈，直到不能弹完为止。

---

解释单调栈为什么是单调的。

指针遍历到 $i$ ,有下标 $x<y$ , $a[x]<a[i]$ 那么 $x$ 就是栈中的合法元素，假设，若有 $a[x]>a[y]$ ,$a[y]$ 比 $a[x] $ 离 $a[i]$ 更近，所以假设不成立，$a[x]<a[y]$ 说明栈中元素是单调递增的。

如果要求右边，就从n到1循环。

求最小，就是 $a[i]<=栈顶元素$ ，哨兵置 -0x3f3f3f3f。

还有一种记忆方法：

stk[++tt] = -0x3f3f3f3f;
fo(i,1,n){ 
    // 一直有-无穷
    while(a[i] <= stk[tt]) // 如果是<=,栈内元素会是严格单调增的
        tt--;
    if(stk[tt] == -0x3f3f3f3f)
        cout<<"-1 ";
    else
        cout<<stk[tt]<<" ";
    stk[++tt]=a[i];
}
1
2
3
4
5
6
7
8
9
10
11

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<<stk[tt]<<" ";
        stk[++tt]=a[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

y总是用栈空不空判断的

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<<stk[tt]<<" ";
        else
            cout<<"-1 ";
        stk[++tt]=a[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

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<<i<<" "<<pre[i]<<" "<<suf[i]<<endl;
            ans = max(ans,(suf[i]-1-(pre[i]+1)+1)*a[i]);
        }
        cout<<ans<<endl;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

总结：单调栈和单调队列都可以叫 双端队列 ， 单调栈可以存值存下标。单调队列为了判断队头何时出队，存数组下标。

152. 城市游戏 （单调栈TRICK题）

N遍直方图中的最大矩形，注意单调栈写带哨兵的

对于每一行，先预处理出up[]来，然后做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<<ans*3<<endl;
}
int main(){
    solve();
    return 0;
}   

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

3780. 构造数组

---

单调栈综合应用。

主要还是思维。

1. 分析题，发现题目一定是单峰的，单调端点算单峰。
2. 枚举峰点，左边数值递增，右边递减，两者独立！
3. 假设分界点是 $i$ , 考虑将 $1\sim i$ 变成非严格递增的最大和。
   1. 顺序考虑不好考虑，逆序考虑。$a[i]=m[i]$ , $a[i-1]=min(m[i-1],a[i])$ …
   2. 对于 $a[i]$ 找到他左边第一个小于他的元素的位置 $j$ , $[j+1,i]$ 应该和 $a[i]$ 相等。
   3. 那么之前的呢？一直跳吗？ 递推！
   4. 设 $L[i]$ 表示将 $1\sim i$ 变成递增（非严格）的最大和。
   5. $L[i]=L[j]+(i-j)\ast a[i]$
4. 同理预处理出 $R[]$
5. 找到分界点，贪心取理论最大值！

注意求 R时，单调栈中的指针是比i指针靠右的，就像求L时，单调栈中的指针比i指针靠左一样！

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<
        r[i] = r[left] + (ll)(left-i)*a[i];
        stk[++tt] = i;
    }
    
    ll res = 0,k;
    for(int i=1;i<=n;i++){
        if(l[i] + r[i] - a[i] > res){
            res = l[i] + r[i] - a[i];
            k = i;
        }
    }
    ans[k] = a[k];
    for(int i=k-1;i>=1;i--){
        ans[i] = min(a[i],ans[i+1]);
    }
    for(int i=k+1;i<=n;i++){
        ans[i] = min(a[i],ans[i-1]);
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<' ';
    }
}

int main(){
    solve();
    return 0;
}   

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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<
    // cout<
    
    fo(i,1,m){
    	ans += (i-l[i]) * (r[i] - i) * (x[i]);
    }
}

void solve(){
    cin>>n>>m;fo(i,1,n)fo(j,1,m){char s;cin>>s;if(s=='.')a[i][j]=1;else a[i][j]=0;}
    fo(i,1,n){
        fo(j,1,m){
            if(a[i][j]){
                up[i][j] = up[i-1][j]+1;
            }
            else up[i][j] = 0;
        }
    }
    fo(i,1,n){
        work(up[i]);
    }
    cout<<ans;
}

int main(){
    solve();
    return 0;
}   

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

双指针

4483. 格斗场

排序后发现，当前数会被后边的数删掉，并且当前数的存在不影响后边的数。

对于 $i$ 找 $1\le a[j]-a[i]\le k$ 的 $j$ , 可以找最小的 $a[j]>a[i]+k$ , 判断 $a[j-1]-a[i]$ 是否大于1。

法一：upper_bound。

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<<n-ans;
}
1
2
3
4
5
6
7
8
9
10
11
12

法二：双指针。

原来双指针while中 j 的限制可以绝对 i和j哪个是尾指针，哪个是头指针

证明正确性：

一般双指针都是找4个指针，然后找一个矛盾。

枚举到 $i$ ,有 $j$ 满足 $a[j]>a[i]+k,a[j]最小$ 。$i$ 向右移动到了 $i^{\prime }$ ,假设有 $j^{\prime }<j$ ,和 $i^{\prime }$ 配对。

发现$a[j-1]-a[i]\le k$ 有，$a[j-1]-a[i^{\prime }]\le k$ , 所以 $i^{\prime }$ 对应的 $J$ 最小也是 $j$ 不是 $j^{\prime }$ ,矛盾，说明，$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<<n-ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15