单调栈（c++）

干货

先讲讲单调栈

单调栈，就是只有递增或递减的栈。（单调递减栈、单调递增栈）

给一个数组，让它们进入单调递减栈的规则是：

如果栈为空，直接进入；

如果要进入的数小于等于栈顶的数，则直接进入；

如果要进入的数大于栈顶的数，就删除栈顶的数，重复直到进入的数小于等于栈顶的数，然后进入。

单调递增栈反之。

题目

每日温度

给定一个数 n ，接下来 n 个数，表示每天的温度，返回一个数组 c ，其中 c [ i ] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用0来代替。

示例 1:
输入:

8

73 74 75 71 69 72 76 73

输出

1 1 4 2 1 1 0 0

示例 2:
输入

4

30 40 50 60
输出

 1 1 1 0

示例 3:
输入:

3

30 60 90
输出:

1 1 0

#include <bits/stdc++.h>
using namespace std;
struct aaaaa
{int aa,ii;
};
stack<aaaaa> b;
int a[100010];
int c[100010];
int n;
int main()
{cin>>n;for(int i = 1;i<=n;i++){cin>>a[i];}for(int i = 1;i<=n;i++){aaaaa w;w.aa = a[i];w.ii = i;if(b.empty()==true) b.push(w);else{if(w.aa<=b.top().aa) b.push(w);else{while(true){if(b.empty()==true||w.aa<=b.top().aa) break;c[b.top().ii] = i-b.top().ii;b.pop();}b.push(w);}}}for(int i = 1;i<=n;i++){cout<<c[i]<<" ";}return 0;
}

柱状图中的最大矩形

#include <bits/stdc++.h>
using namespace std;
struct aaaaa
{int aa,ii;
};
stack<aaaaa> b;
int a[100010];
int n;
int ma,cnt;
int main()
{cin>>n;for(int i = 1;i<=n;i++){cin>>a[i];}a[++n] = 0;for(int i = 1;i<=n;i++){aaaaa w;w.aa = a[i];w.ii = i;if(b.empty()==true) b.push(w);else{if(w.aa>=b.top().aa) b.push(w);else{while(true){if(b.empty()==true||w.aa>=b.top().aa) break;ma = max(ma,(i-b.top().ii)*b.top().aa);b.pop();}b.push(w);}}}cout<<ma;return 0;
}