卖手表的网站,南京医院网站建设方案,青岛专业网站建设推广报价,wordpress怎么增加菜单链接#xff1a; 文章目录题目描述题解#xff1a;代码#xff1a;小A的柱状图时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述
柱状图是有一些宽度相等的矩形下端对齐以后…链接
文章目录题目描述题解代码小A的柱状图时间限制C/C 1秒其他语言2秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述
柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形但是小A的柱状图却不是一个规范的柱状图它的每个矩形下端的宽度可以是不相同的一些整数分别为a[i]a[i],每个矩形的高度是h[i]h[i],现在小A只想知道在这个图形里面包含的最大矩形面积是多少。
输入描述: 一行一个整数N表示长方形的个数 接下来一行N个整数表示每个长方形的宽度 接下来一行N个整数表示每个长方形的高度 输出描述: 一行一个整数表示最大的矩形面积 示例1 输入 复制
7
1 1 1 1 1 1 1
2 1 4 5 1 3 3输出 复制
8说明 样例如图所示包含的最大矩形面积是8 备注: 1≤n≤1e6,1≤a[i]≤100,1≤h[i]≤1e9
题解
单调栈问题 我们可以用一个单调栈来维护每个矩阵的高度和宽度 当前矩阵高于栈顶进栈 当前矩阵a小于栈顶时直到栈为空或者栈顶矩形的高度比当前矩形小。在出栈过程中我们累计被弹出的矩形的宽度和。每弹出一个矩形就用他的高度他指被弹出的矩阵乘上累计的宽度取更新答案因为每次弹出的高度要比上次弹出的小相当于依次求以从左往右以每个矩阵高的面积如图所示。整个出栈过程结束后我们把一个高度为当前矩阵高度宽度为累计值的新矩阵入栈。
全部扫描过后我们要将栈内剩余矩阵依次弹出并利用相同的方法更新答案。
代码
#includebits/stdc.h
#includestack
using namespace std;
typedef long long ll;
const int maxn1e64;
int a[maxn];
ll h[maxn];
stackint s;
stackint w;//宽度
int main()
{int n;cinn;for(int i1;in;i)cina[i];for(int i1;in;i)cinh[i];h[n1]0;ll ans0;s.push(0);//先放一个0 w.push(0); for(int i1;in;i){if(h[i]s.top()){s.push(h[i]);w.push(a[i]);}else {ll tot0;while(!s.empty()s.top()h[i]){totw.top();ansmax(ans,tot*s.top());w.pop();s.pop();}s.push(h[i]);w.push(tota[i]);}}coutans;return 0;
}
