CSP认证201312-3最大的矩形[C++题解]：枚举

125 阅读 0 评论 83 点赞

我是靠谱客的博主矮小毛豆，这篇文章主要介绍CSP认证201312-3最大的矩形[C++题解]：枚举，现在分享给大家，希望可以做个参考。

文章目录

- - 题目解答
  - 题目链接

题目解答

在这里插入图片描述

来源：acwing

分析：面积最大，下边界一定是直方图的最下边，上边界一定和某个长条高度重合。这样枚举所有的高度，同时看左右宽度能够到哪儿，这样就可以通过长*宽算出来面积,然后取一个最大的即可。

时间复杂度 $O(n^2)$

ac代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;

int n;
int h[N]; //高度

int main(){
    cin >> n;
    for(int i =1; i<= n; i++) cin >>h[i];
    int res = 0;
    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++;
        res = max(res, h[i] *(r- l -1)); //取最大的面积
    }
    cout << res << endl;
}