题目
链接:https://ac.nowcoder.com/acm/contest/28537/Q
来源:牛客网时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld题目描述
柱状图是有一些宽度相等的矩形下端对齐以后横向排列的图形,但是小A的柱状图却不是一个规范的柱状图,它的每个矩形下端的宽度可以是不相同的一些整数,分别为a[i]a[i]a[i],每个矩形的高度是h[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]≤1e91 \leq n \leq 1e6 , 1\leq a[i] \leq 100 ,1\leq h[i] \leq 1e91≤n≤1e6,1≤a[i]≤100,1≤h[i]≤1e9
题解
突破点一:
它只告诉了每一个长方形的宽,没有办法直接求出老多个长方形的宽
所以我使用前缀和…
突破点二:
记住:单调栈可以解决
- 左/右第一个比他小/大的
- 排队问题中有没有人插队
这里,我从左往右来枚举方格,让他向左,向右扩展!
代码
#include <iostream>
#include <stack>
using namespace std;
typedef long long LL;
const int MAX = 1e6 + 7;
int a_origin[MAX];
int a[MAX];
int h[MAX];
int left_[MAX];//左边比他小的方格所对应的前缀和
int right_[MAX];//右边比他小的方格所对应的前缀和
int main()
{
LL ans = 0;
ios::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a_origin[i];
a[i] = a_origin[i] + a[i - 1];
}
for (int i = 1; i <= n; i++)
{
cin >> h[i];
}
{
//stack没有清空的选项,我只得创建代码块,让系统清除
stack<int>st;
for (int i = n; i > 0; i--)
{
while (!st.empty() && h[i] <= h[st.top()])
st.pop();
if (st.empty())
{
right_[i] = n + 1;//!!!!!!!!!!
st.push(i);
}
else
{
right_[i] = st.top();
st.push(i);
}
}
}
{
stack<int>st;
for (int i = 1; i <= n; i++)
{
while (!st.empty() && h[i] <= h[st.top()])
st.pop();
if (st.empty())
{
left_[i] = 0;//!!!!!!!!!!
st.push(i);
}
else
{
left_[i] = st.top();
st.push(i);
}
}
}
for (int i = 1; i <= n; i++)
{
LL tmp = (a[right_[i]-1] - a[left_[i]])*h[i];
ans = max(tmp, ans);
}
cout << ans;
return 0;
}