CCF CSP 201312-3.最大的矩形

问题描述

　　在横轴上放了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

---

分析：

定义一维int型数组h，用于存储所有的矩形高度；int型变量maxArea表示最大矩形的面积；

int型变量minHeight，表示从第i个矩形到第j个矩形中的最小高度。

遍历给定的n个矩形：从矩形i出发，向后寻找，

计算从第i个矩形到第j个矩形中，能够容纳的矩形面积area = minHeight * (j - i + 1) 。

若area > maxArea，则令maxArea = area。

• C++版

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	int h[n];
	for (int i = 0; i < n; i++) {
		scanf("%d", &h[i]);
	}
    
	int area, maxArea = 0, minHeight;
	for (int i = 0; i < n; i++) {
		minHeight = h[i];
		for (int j = i; j < n; j++) {
			minHeight = min(minHeight, h[j]);
			area = (j - i + 1) * minHeight;
			if (area > maxArea) {
				maxArea = area;
			}
		}
	}
	printf("%d\n", maxArea);
	return 0;
}

• Java版

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] h = new int[n];
		for (int i = 0; i < h.length; i++) {
			h[i] = scan.nextInt();
		}
		scan.close();
        
		int area, maxArea = 0, minHeight;
		for (int i = 0; i < h.length; i++) {
			minHeight = h[i];
			for (int j = i; j < h.length; j++) {
				minHeight = Math.min(minHeight, h[j]);
				area = (j - i + 1) * minHeight;
				if (area > maxArea) {
					maxArea = area;
				}
			}
		}
		System.out.println(maxArea);
	}
}