SCAU 9715 相邻最大矩形面积

红太狼 2023-10-03 17:40 100阅读 0赞

### 9715 相邻最大矩形面积 ###

时间限制:1000MS 代码长度限制:10KB  
提交次数:0 通过次数:0

题型: 编程题 语言: G++;GCC;VC;JAVA

Description  
在X轴上水平放置着 N 个条形图，这 N 个条形图就组成了一个柱状图，每个条形图都是一个矩形，每个  
矩形都有相同的宽度，均为1单位长度，但是它们的高度并不相同。  
例如下图，图1包含的矩形的高分别为2，1，4，5，1，3，3 单位长度，矩形的宽为1单位长度。

你的任务就是计算柱状图中以X轴为底边的最大矩形的面积。图2阴影部分就是上述例子的最大矩形面积。

输入格式  
输入数据的第一行是一个整数 N(1≤ N ≤100000)，表示柱状图包含 N 个矩形。  
紧接着 N 个整数h1,…,hn(0≤ hi ≤20000, 1≤ i≤ N)，表示柱状图中按从左到右顺序给出的矩形  
的高度。矩形的宽度为1。

输出格式  
输出一个整数S，表示以X轴为底边的最大矩形的面积。

输入样例  
7  
2 1 4 5 1 3 3

输出样例  
8

提示

这个问题，用简单的方法分析，寻找相邻几个矩形竖条最矮个构成的大矩形。O(n^2)的算法是比较容易实现的。

#include <iostream>
    using namespace std;
    int main() {
        
        int n;
        cin>>n;
        int h[n];
        for(int i = 0;i<n;i++){
        
            cin>>h[i];
        }
        int minH ;
        int maxArea =0;
        for(int i =0;i<n;i++){
        
            minH = h[i];
    
            for(int j=i+1;j<n;j++){
        
    //            cout<<"i:"<<i<<"  j:"<<j<<"  minH:"<<minH<<endl;
                    if(h[j]<minH){
        
                        minH = h[j];
    //                    cout<<"???";
    //                    cout<<"i:"<<i<<"  j:"<<j<<"  minH:"<<minH<<endl;
                    }
                    int area = (j-i+1)*minH;
    
                    if(area>maxArea){
        
                        maxArea = area;
    
                    }
            }
        }
        cout<<maxArea<<endl;
    
        return 0;
    }