问题描述

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

解题思路

从高度为1开始，找当前高度的最大矩形面积。高度依次增加直到最高。

参考代码

#include<iostream>
#include<math.h>
using namespace std;
int n, h[1005];
int maxx = 0;
int ans = 0;
void judg(int heigh)
{
    int tmp = 0;
    int curmax = 0;
    for (int i = 0; i < n; i++) {
        if (h[i] >= heigh) {
            tmp += heigh; 
        } 
        else {//当前未达到高度 ，将之前得到的最大矩形进行记录 
            curmax = max(tmp, curmax);
            tmp = 0;//待下一轮统计 
        }
    }
    curmax = max(tmp, curmax);//注意，高度为1的不会走else，需要单独拿出来比较一次，存值到curmax；或者直到最后一个高度才符和，未走else，也要经过这一步 
    ans =  max(ans, curmax);//与其他层进行比较 
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        maxx = max (maxx, h[i]);//存储最大高度 
    }
    for (int i = 1; i <= maxx; i++) {//分别找到对应高度的最大矩形 
        judg(i);
    }
    cout <<ans;
    return 0;
}