题意
给你一连串的矩形的高度, 他们宽的长度都是 1, 求组成的最大矩形的面积.
解题思路
其实就是求以每个数为最小值时, 这个区间范围是什么?
暴力肯定不行, 因为复杂度为 O(N^2), 会超时, 所以我们要寻找一个更加好的办法. 这里单调栈就显示出来优势了. 我们可以达到 O(N) 的复杂度来实现这个操作.
代码实现
- #include<cmath>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<iostream>
- #include<string>
- #include<stack>
- #include<queue>
- #include<map>
- typedef long long ll;
- using namespace std;
- const double esp=1e-6;
- const int inf=0x3f3f3f3f;
- const int MAXN=1E5+7;
- ll num[MAXN], st[MAXN];
- int n, top, lt[MAXN], rt[MAXN];
- int main()
- {
- while(scanf("%d",&n) && n!=0)
- {
- top=1;
- st[top]=0;
- num[0]=-1; num[n+1]=-1;
- for(int i=1; i<=n; i++)
- scanf("%lld", &num[i]);
- for(int i=1; i<=n+1; i++)
- {
- lt[i]=i;// 最差就是这种情况
- rt[i]=i;
- while(num[st[top]]> num[i])// 单调不减的栈
- {
- lt[i] = lt[st[top]]; // 我们可以确定当前的 i 的最左边是栈顶元素的最左边
- rt[st[top]] = i-1; // 而栈顶元素的最右边就是 i-1
- top--;
- }
- if(num[st[top]] == num[i]) lt[i] = lt[st[top]]; // 和栈顶元素相等的时候
- st[++top]=i;
- }
- // for(int i=1; i<=n; i++)
- // printf("%d %d\n", lt[i], rt[i]);
- ll ans=-1;
- for(int i=1; i<=n; i++)
- {
- ans = max(ans, (rt[i] - lt[i] + 1)*num[i] );
- }
- printf("%lld\n", ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3415400.html