CCF试题--最大的矩形

57 阅读 0 评论 38 点赞

我是靠谱客的博主谦让鸡翅，最近开发中收集的这篇文章主要介绍CCF试题--最大的矩形，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述
　　在横轴上放了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

我的答案（java实现）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class MaxRectangle {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int N;// 记录矩形个数
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            String strs = br.readLine();// 记录输入的各个矩形高度
            String str = strs.replace(" ", "");// 去掉空格
            int num[] = new int[str.length()];// 用数组存放数据
            // 将字符转换成int，放入数组中
            for (int i = 0; i < str.length(); i++) {
                num[i] = (int) str.charAt(i) - 48;
            }
            int maxSize[] = new int[num.length];// 记录每个矩形为中心的最大面积
            // 从前向后依次扫描，找出每个矩形为开始的右半部分的最大面积
            for (int i = 0; i < num.length; i++) {
                int record = 0;// 记录一共经过了几个比该矩形高或等高的矩形数（包括自己）
                for (int j = i; j <= num.length - 1; j++) {
                    if (j == num.length - 1) {// 最后一个矩形特殊处理，如果最后一个仍大于等于本矩形，则最大面积也包括它
                        if (num[i] <= num[j]) {
                            record++;
                            maxSize[i] = num[i] * record;
                            break;
                        }
                    }
                    if (num[i] > num[j]) {// 如果后面的矩形比本矩形小，则达到最大面积了，计算一共经过
                                            // 了多少个大于等于本矩形的，计算最大面积：本矩形的高*经过的个数（因为每个矩形的宽为1）
                        maxSize[i] = num[i] * record;
                        break;// 计算下一个矩形为标志的最大面积
                    } else {// 如果后面的矩形大于等于本矩形，则经过它，记录加1
                        record++;
                    }
                }
            }
            // 与上面对应，从后向前扫描，找出每个矩形为开始的左半部分的最大面积，二者加起来，构成以本矩形为中心的最大面积
            for (int i = num.length - 1; i >= 0; i--) {
                int record = -1;// 记录一共经过了几个比该矩形高或等高的矩形数（不包括自己，因为从前向后时，已经包括了）
                for (int j = i; j >= 0; j--) {
                    if (j == 0) {// 最前一个矩形特殊处理，如果最前一个仍大于等于本矩形，则最大面积也包括它
                        if (num[i] <= num[j]) {
                            record++;
                            maxSize[i] = maxSize[i] + num[i] * record;
                            break;
                        }
                    }
                    if (num[i] > num[j]) {// 如果前面的矩形比本矩形小，则达到最大面积了，计算一共经过
                                            // 了多少个大于等于本矩形的，计算最大面积：本矩形的高*经过的个数（因为每个矩形的宽为1）
                        maxSize[i] = maxSize[i] + num[i] * record;
                        break;
                    } else {// 如果前面的矩形大于等于本矩形，则经过它，记录加1
                        record++;
                    }
                }

            }
            // 找出最大面积
            int max = -1;
            for (int i = 0; i < maxSize.length; i++) {
                if (maxSize[i] > max) {
                    max = maxSize[i];
                }
            }
            System.out.print(max);// 输出最大面积

        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

}