C++ //CCF-CSP计算机软件能力认证 201312-3 最大的矩形

CCF-CSP计算机软件能力认证 201312-3

最大的矩形

问题描述

             在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第 i （ 1 ≤ i ≤ n ） i（1 ≤ i ≤ n） i（1≤i≤n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

             请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。

输入格式

             第一行包含一个整数n，即矩形的数量 ( 1 ≤ n ≤ 1000 ) (1 ≤ n ≤ 1000) (1≤n≤1000)。
             第二行包含n 个整数 h 1 , h 2 , … , h n h_1, h_2, … , h_n h1​,h2​,…,hn​，相邻的数之间由空格分隔。 ( 1 ≤ h i ≤ 10000 ) (1 ≤ h_i ≤ 10000) (1≤hi​≤10000)。 h i h_i hi​是第i个矩形的高度。

输出格式

             输出一行，包含一个整数，即给定直方图内的最大矩形的面积。

样例输入

       6
       3 1 6 5 2 3

样例输出

       10

环境：Linux Ubuntu（云服务器）

工具：vim

代码块：

方法：

/*************************************************************************
	> File Name: ex20131203.cpp
	> Author: 
	> Mail: 
	> Created Time: Tue 26 Mar 2024 10:54:45 AM CST
 ************************************************************************/

#include<iostream>
using namespace std;

int main(){
    int n;
    cin>>n;

    const int N = n;
    int h[N];
    for(int i = 0; i < n; ++i){
        cin>>h[i];
    }

    int base, tempArea, area = 0;
    int left, right;
    for(int i = 0; i < n; ++i){
        base = h[i];
        tempArea = base;
        left = i - 1;
        right = i + 1;
    
        while(left >= 0 && h[left] >= h[i]){
            tempArea += base;
            --left;
        }
        
        while(right < n && h[right] >= h[i]){
            tempArea += base;
            ++right;
        }
        
        if(tempArea > area){
            area = tempArea;
        }
    }

    cout<<area<<endl;

    return 0;
}