前言:

时隔两天再次写起了博客，最近学习积极性越来越低迷了。

为了我的未来，一定要变得自律起来。废话不多说，今天复习的内容是单调栈

概述:

单调栈一般用于解决与下一个更大元素（有关的问题，包括以下几类：

1.寻找每个元素的下一个更大元素。
2.寻找每个元素的下一个更大或相等元素。
3.寻找每个元素的下一个更小元素或更小或相等元素。
在这些问题中，单调栈维护一个单调递增或递减的栈，将元素依次压入栈中。对于每个新元素，我们可以在栈中弹出所有比它小的元素，并将它们的“下一个更大/小元素”设置为当前元素。

实践

直接上一道牛客偏难的题目，当初没想到用单调栈解决

题目:最优屏障

M国的地势高低不平，现给出一个数组代表此国家某纬度上均匀分布的N座山的海拔高度Hi，已知每座山的山顶上都有一座哨塔，若两个哨兵分别位于第i、j(i<j)座山上，当且仅当两人所在的山比两人之间所有的山都高时，这两个哨兵可以相互监视，M国的防守能力大小为相互监视的哨兵对数。H国早已对M国虎视眈眈，H国的皇帝希望黑魔法师们可以在M国的某两座山之间放置一块巨大的屏障,M国的哨兵不可通过该屏障互相监视。皇帝想让你告诉他最优的屏障放置位置，你是皇帝手下最信任的军师，现在需要你帮助皇帝计算最优的屏障放置位置和最大的防守力减少量。

思路

维护一个栈分别计算第i座山左右两边能够守望的山数。又因为要计算放置最优屏障后最大防守力减少值，

所以只需要用最大防守力将去屏障两边的左右防守力，即第i个位置的左右两边的能到达的防守力。

所以我们不仅要算出第i坐山的防守力，同时还有两个前缀和数组（一个是从第1到第i的防守力，另一个是第i到第1的防守力）即可算出最优屏障左右两边减少的防守力

代码实现

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
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N],ln[N],rn[N];

void solve(int m){
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    memset(ln,0,sizeof ln);
    memset(rn,0,sizeof rn);
    stack<int>st;
    for(int i=1;i<=n;i++){
        ln[i]=ln[i-1];
        while(st.size()&&st.top()<a[i])
            ln[i]++,
            st.pop();
        if(st.size())ln[i]++;
        st.push(a[i]);
    }
    while(st.size())st.pop();
    for(int i=n;i>=1;i--){
        rn[i]=rn[i+1];
        while(st.size()&&st.top()<a[i])
            rn[i]++,
            st.pop();
        if(st.size())rn[i]++;
        st.push(a[i]);
    }
    int ans=-1,idx=0;
    for(int i=1;i<=n;i++){
        int temp=ln[n]-(ln[i-1]+rn[i]);
        if(temp>ans)ans=temp,idx=i;
    }
    printf("Case #%d: %d %d\n",m,idx,ans);
}
int main(){
    int T;cin>>T;
    for(int m=1;m<=T;m++){
        solve(m);
    }
    return 0;
}