首页 > 代码库 > 9715 相邻最大矩形面积 单调栈
9715 相邻最大矩形面积 单调栈
9715 相邻最大矩形面积
时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC;VC;JAVA
Description
在X轴上水平放置着 N 个条形图，这 N 个条形图就组成了一个柱状图，每个条形图都是一个矩形，每个 矩形都有相同的宽度，均为1单位长度，但是它们的高度并不相同。 例如下图，图1包含的矩形的高分别为2，1，4，5，1，3，3 单位长度，矩形的宽为1单位长度。
你的任务就是计算柱状图中以X轴为底边的最大矩形的面积。图2阴影部分就是上述例子的最大矩形面积。
输入格式
输入数据的第一行是一个整数 N(1≤ N ≤100000)，表示柱状图包含 N 个矩形。 紧接着 N 个整数h1,...,hn(0≤ hi ≤20000, 1≤ i≤ N)，表示柱状图中按从左到右顺序给出的矩形 的高度。矩形的宽度为1。
输出格式
输出一个整数S，表示以X轴为底边的最大矩形的面积。
输入样例
7 2 1 4 5 1 3 3
输出样例
8
提示
这个问题，用简单的方法分析，寻找相邻几个矩形竖条最矮个构成的大矩形。O(n^2)的算法是比较容易实现的。
用单调栈维护，dp[i][0]表示向左，第一个小于a[i]的数，dp[i][1]表示向右，第一个小于a[i]的数。
那么区间内的就是以a[i]为高的ans。
然后枚举每一个a[i]统计答案即可。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 100000 + 20; int dp[maxn][2]; int a[maxn]; int stack[maxn]; int id[maxn]; int n; void work() { for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } a[n + 1] = -1; int top = 1; stack[top] = a[1]; id[top] = 1; for (int i = 2; i <= n + 1; ++i) { while (top >= 1 && a[i] < stack[top]) { dp[id[top]][1] = i; top--; } ++top; stack[top] = a[i]; id[top] = i; } top = 1; stack[top] = a[n]; id[top] = n; for (int i = n - 1; i >= 0; --i) { while (top >= 1 && a[i] < stack[top]) { dp[id[top]][0] = i; --top; } ++top; stack[top] = a[i]; id[top] = i; } // for (int i = 1; i <= n; ++i) { // printf("%d***\n", dp[i][0]); // } int ans = 0; for (int i = 1; i <= n; ++i) { int t = dp[i][1] - i + i - dp[i][0] - 1; ans = max(ans, t * a[i]); } printf("%d\n", ans); } int main() { #ifdef local freopen("data.txt","r",stdin); #endif while (scanf("%d", &n) != EOF) work(); return 0; }
9715 相邻最大矩形面积 单调栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。