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

本文主要是介绍CSP认证201312-3最大的矩形[C++题解]：枚举，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目解答

来源：acwing

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

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

ac代码

#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;
}

题目链接

https://www.acwing.com/problem/content/3197/

这篇关于CSP认证201312-3最大的矩形[C++题解]：枚举的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---