最大的矩形


一、题目描述

题目链接

题目描述

题目描述


二、分析

  • 首先看数据范围:1<= n <= 1000 && 1<= hi <= 10000 ,需要时间复杂度小于等于 O(n2)
  • 确定枚举的对象,本题中可以枚举矩形的上边界。知道矩形的上边界和左右边界之后就可以确定一个矩形。枚举矩形的上边界,设横坐标为 i ,高度为 h,经过观察可以发现,上边界确定之后,以该边为上边界的最大矩形就可以确定:左边界为 i 前左数高度第一个小于 h 的;右边界为i 后往右数高度第一个小于 h 的。之后更新最大矩形。

三、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1020;
int n,re,ans;
int h[N];
int main(){
cin>>n;
for(int i = 1;i<= n;i++){
cin>>h[i];
}
//枚举上边界
for(int i = 1;i<= n;i++){
int l = i,r = i;
//搜索左边界
while(l>= 1 && h[l]>= h[i]){
l--;
}
//搜索右边界
while(r <= n && h[r] >= h[i]){
r++;
}
//计算矩形面积,注意r - l之后需要减1.
re = (r - l - 1)*h[i];
ans = max(re,ans);
}
cout<<ans<<endl;
return 0;
}
0%