【c++提高1】单调栈

大纲

1.单调栈简介&前言
2.例题
3.使用单调栈解决问题

1.单调栈简介&前言

单调栈是栈的一种特殊的形式，必须要求栈内元素单调，当题目有单调性的话（不是答案具有单调性，是信息具有单调性），一般可以使用单调栈，避免重复执行不必要的操作，从而将时间复杂度降低。
单调栈没有什么特定的算法，也没有啥模板 ，所以就不讲太多关于单调栈算法一类的东西了 就将一些例题吧。

2.例题

(1).最近的数

给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。

输入格式
第一行包含整数N，表示数列长度。

第二行包含N个整数，表示整数数列。

输出格式
共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。

数据范围
1≤N≤10 ^ 5
1≤数列中元素≤10 ^ 9
样例

输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思路1.暴力

暴力枚举！

每一次输入一个数，从i-1一直开始找，如果当前找到的一个数

时间复杂度：

输入的for循环，O(n)
查找a[j] 总时间复杂度：O(n ^ 2)

但是n的范围是10 ^ 5，时间复杂度：O(10 ^ 10)，计算机1ms大概能运算10 ^ 7 ~ 10 ^ 8，TTTTTLLLLLEEEEE！！！！！

思路2.单调栈

就直接讲一下怎么写吧，等一会我再讲一下为什么。

算法过程：
定义一个栈，并且记录栈顶tops
for循环，输入每一个数
不停的出栈，直到栈顶

现在我们要确定这个算法的正确性，关键在于我们每一次出栈的元素是否会在后面的过程中作为答案输出：

现在假设按照算法的过程，判断后面一个数是否会用到前面出栈的元素。三种情况：
① 后面一个元素=当前元素，答案就是当前栈顶，没有问题。
② 后面一个元素<当前元素，出栈的元素都>=当前元素，那么那些出栈元素也一定>=后面的元素（设出栈的元素为P，当前元素为A，后面的元素为B：A>=B,P>=A则P一定>=B）
③ 后面一个元素>当前元素，若出栈的元素<后面的元素，但是他们一定>=当前元素，所以当前元素一定比出栈的元素更优。否则答案显然不可能是那些出栈的元素。

这样我们就证明了算法的正确性。
样例模拟：

第一次：栈为空，将3入栈，输出-1。 第二次：3<4，直接输出3，并且将4入栈。 第三次：将3, 4出栈，栈空了，输出-1，并且将2入栈。
第四次：2<7，直接输出2，并且将7进栈。 第五次：2同样满足，输出2

AC代码：

#include 
using namespace std;
const int N = 1e5 + 10;
int n, x, s[N], tops;       //定义栈，并且记录栈顶 
int main ()
{
	cin >> n;
	while (n -- )
	{
		cin >> x;           //读入
		while (tops && s[tops] >= x) tops --;   //维护栈内元素单调
		if (tops) cout << "-1 ";                //没有一个元素
		else cout << s[tops] << ' ';            //否则有解，则输出
		s[++ tops] = x;                         //元素入栈 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(2).最大子矩阵

电子屏是安装在城市的建筑物上，城市里有紧靠着的N个建筑。需要在上面找一块尽可能大的矩形放置电子屏。我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度H1,H2…HN，且0<Hi<=1,000,000,000，并且我们假设每个建筑物的宽度均为1。要求输出广告牌的最大面积。



输入

第一行是一个数n (n <= 10 ^ 5）

第二行是n个数，分别表示每个建筑物高度H1,H2…HN，且0<Hi<=1,000,000,000。
输出
一共有一行，表示广告牌的最大面积。	
样例输入

6
5 8 4 4 8 4

样例输出

24


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路1.暴力

枚举一个点i，试着向两边扩展，知道不能扩展为止，最后计算一下面积，取max。
枚举i即可。

1.枚举一个i (1<=i<=n)
2.向左边扩展，枚举一个j (1<=j<=i-1)，必须要满足
h[j]>=h[i]，否则结束扩展
3.向右边扩展，枚举一个j (1<=j<=i-1)，必须要满足
h[j]>=h[i]，否则结束扩展
4.计算面积，将宽度 * h[i]并取max

时间复杂度：

枚举i：O(n)
向两边扩展：O(n)
总时间复杂度：O(n^2)

但是n的范围是10 ^ 5，时间复杂度：O(10 ^ 10)，计算机1ms大概能运算10 ^ 7 ~ 10 ^ 8，超时！
TLE代码：

#include 
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
ll h[N], n, maxs;
int main ()
{
	cin >> n;
	for (int i = 1; i <= n; i ++ ) cin >> h[i];
	for (int i = 1; i <= n; i ++ )
	{
		int cnt = 1;
		for (int j = i - 1; j >= 1; j -- )
		{
			if (h[j] >= h[i]) cnt ++;
			else break;
		}
		for (int j = i + 1; j <= n; j ++ )
		{
			if (h[j] >= h[i]) cnt ++;
			else break;
		}
		maxs = max (maxs, (ll)cnt * h[i]);
	}
	cout << maxs;
}
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

思路2.单调栈

在暴力的基础上，试着用一些方法优化一些操作。
首先第一层for循环：O(n)，是不可能去掉的。
所以说优化的重任就落在了第二层枚举j的for循环身上了

第二层for循环的作用是看i最多能延申到哪里
抽象一下这一步操作：
1.找到i前面离i最近的一个h[j] 2.反向找，找到i后面离i最近的一个h[j] 这个时候就可以发现了：其实就是上一个问题的再反着求一遍。

因为要求两遍，可以使用数组存储单调栈得到的结果，接下来每一次计算面积取max即可。
注意：每一次计算后需要将栈清空。
AC代码：

#include 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
stack < int > stk;
int l[N] , r[N] , a[N];
int n;
void Clear (stack<int>& stk)          //定义Clear函数进行清空操作 
{
	while (! stk.empty ()) stk.pop ();
}
int main ()
{
	cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];   //读入 
    Clear (stk);       //清空 
    for (int i = 1; i <= n; i++) {
        while (! stk.empty () && a[stk.top ()] >= a[i]) stk.pop ();   //维护栈内单调 
        if (! stk.empty ()) l[i] = stk.top ();      //记录 
        else l[i] = 0;                 //说明可以一直延申到最前面，所以直接设为0即可 
        stk.push (i);                  //因为这道题是需要直到延申的位置，所以存入位置即可                 
    }
    Clear (stk);       //清空 
    for (int i = n; i >= 1; i -- )
	{
        while (! stk.empty () && a[stk.top ()] >= a[i]) stk.pop (); //维护栈内单调 
        if (! stk.empty ()) r[i] = stk.top ();  //记录 
        else r[i] = n + 1;             //说明可以一直延申到最后，所以直接设为n+1即可 
        stk.push (i);                  //因为这道题是需要直到延申的位置，所以存入位置即可 
    }
    ll res = 0;
    for (int i = 1; i <= n; i ++ ) res = max (res , (ll)a[i] * (r[i] - l[i] - 1));  //计算面积取max 
    cout << res;
}

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

关于单调栈时间复杂度：
由于每个元素最多各自进出栈一次，忽略常数（进栈），时间复杂度是O(n)。
单调栈基本上就是这样吧，一些题目可以套用单调栈的话就用吧，话说还是有一个板子的 （其实就是第一题的代码）：

#include 
using namespace std;
const int N = 1e5 + 10;
int n, x, s[N], tops;
int main ()
{
	cin >> n;
	while (n -- )
	{
		cin >> x;
		while (tops && s[tops] >= x) tops --;
		if (tops) cout << "-1 ";
		else cout << s[tops] << ' ';
		s[++ tops] = x;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.使用模板 单调栈解决问题

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

 

提示：

    n == height.length
    1 <= n <= 2 * 104
    0 <= height[i] <= 105
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

来源于leetcode
维护一个单调递减栈，找到找到左边第一个比自己高的柱子。
用下标计算出宽度，最后深度×宽度得接水量。
代码：

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st; //单调栈内存放元素下标
        st.push(0);  //放入第一个元素
        int sum = 0;
        for (int i = 1; i < height.size(); i ++) {
            if (st.empty() || height[i] <= height[st.top()]) {
                st.push(i);
            }
            else {
                while (!st.empty() && height[i] > height[st.top()]) {
                    int index = st.top(); //栈顶元素出栈并记录下标
                    st.pop();
                    if (!st.empty()) {
                        int w = i - st.top() - 1;           //凹槽宽
                        int h = min(height[i], height[st.top()]) - height[index]; //凹槽高
                        sum += w * h;       //累加所有接水量
                    }
                }
            }
            st.push(i);
        }
        return sum;
    }
};
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