試題編號：	201312-3
試題名稱：	最大的矩形
時間限制：	1.0s
內存限制：	256.0MB
問題描述：	問題描述 　　在橫軸上放了n個相鄰的矩形，每個矩形的寬度是1，而第i（1 ≤ i ≤ n）個矩形的高度是hi。這n個矩形構成了一個直方圖。例如，下圖中六個矩形的高度就分別是3, 1, 6, 5, 2, 3。 　　請找出能放在給定直方圖里面積最大的矩形，它的邊要與坐標軸平行。對于上面給出的例子，最大矩形如下圖所示的陰影部分，面積是10。 輸入格式 　　第一行包含一個整數n，即矩形的數量(1 ≤ n ≤ 1000)。 　　第二行包含n 個整數h1, h2, … , hn，相鄰的數之間由空格分隔。(1 ≤ hi?≤ 10000)。hi是第i個矩形的高度。 輸出格式 　　輸出一行，包含一個整數，即給定直方圖內的最大矩形的面積。 樣例輸入 6 3 1 6 5 2 3 樣例輸出 10

問題鏈接：CCF201312試題。

問題描述：首先輸入正整數n，接著輸入n個正整數表示直方圖的一個高度，計算這些直方圖中的最大矩形面積。（詳見原問題，點擊上面的鏈接）。

問題分析：解決這個問題，一種是用暴力法（枚舉法）來解決，任何一個矩形必然始于第i個直方圖，終止于第j塊直方圖（i<=j），從所有這些面積中找出最大矩形面積即可；另外一種辦法是對這n個數只看一遍，就算出最大矩形面積，其計算復雜度為O(n)，相比較而言，算法要復雜一些，還需要付出空間的代價。

程序說明：本程序采用暴力法實現，數據用數組來存儲。另外一種數據存儲方法是使用STL的包裝類vector，可以實現動態數據存儲，不受限于數據的多少。

參見：CCF201312-3 最大的矩形（解法二）（100分）。

提交后得100分的C++語言程序如下：

/* CCF201312-3 最大的矩形 */#include <iostream>using namespace std;const int N = 1000; int h[N];int main() {int n, ans, height, area;// 輸入數據cin >> n;for(int i=0; i<n; i++)cin >> h[i];// 計算最大矩形面積：暴力法（枚舉法）ans = 0;for(int i=0; i<n; i++) {height = h[i];for(int j=i; j<n; j++) {if(h[j] < height)height = h[j];area = (j - i + 1) * height;if(area > ans)ans = area;}}// 輸出結果cout << ans << endl;return 0; }

轉載于:https://www.cnblogs.com/tigerisland/p/7564194.html

總結

以上是生活随笔為你收集整理的CCF201312-3 最大的矩形（100分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。