题目原文
问题描述（题目链接登陆账号有问题，要从这个链接登陆，然后点击“模拟考试”，进去找本题目）
| 试题编号： | 201312-3 |
| 试题名称： | 最大的矩形 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： |
问题描述
在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是hi。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。 请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。 第二行包含n 个整数h1, h2, … , hn，相邻的数之间由空格分隔。(1 ≤ hi ≤ 10000)。hi是第i个矩形的高度。 输出格式 输出一行，包含一个整数，即给定直方图内的最大矩形的面积。 样例输入 6 3 1 6 5 2 3 样例输出 10 |
题目大意
先输入n，之后给你n个数字hi（h0,h1,h2...hn-1）。每个数字代表矩形的高，n个底座为1长度，高为给定数值hi高度的矩形，沿着x轴横向向右无缝衔接。让你求出此图形构成的最大矩形面积。
解题思路
两次遍历，第一次遍历n个数值，"i" 作为变量，对于每个数值进行二次遍历，“j”作为变量，即向左和向右总共有多少比“i”变量对应的“hi”数值大的，遇到第一个比这个“hi”小的则停止，最后左右两个方向得到的格子数相加，作为矩形一条边（底），再用“i”作为另一条边（高），相乘得矩形面积
AC代码
1 #include<cstdio>
2 #include<cstring>
3 int map[10500];
4 int maxhigh, minhigh;
5 int answer;
6 int main()
7 {
8 int n;
9 while(scanf("%d", &n) != EOF){
10 memset(map, 0, sizeof(map));
11 for(int i = 0; i < n; i ++)
12 scanf("%d", &map[i]);
13 for(int i = 0; i < n; i ++){
14 int left = 0, right = 0;
15 int flag = i;
16 while(flag >= 0 && map[flag] >= map[i]){
17 if(flag != i)
18 left ++;
19 flag --;
20 }
21 flag = i;
22 while(flag < n && map[flag] >= map[i]){
23 if(flag != i)
24 right ++;
25 flag ++;
26 }
27 if((right + left + 1) * map[i] > answer)
28 answer = (right + left + 1) * map[i];
29 }
30 printf("%d\n", answer);
31 }
32 }
附录
思路1：
读完题最先想到暴力，但想错了，想的是先从下（最低高度hi）往上（最高高度hi）遍历，再遍历n。明显复杂度达到了10^7，正常1s也就是10^7左右（可能会更大数量10^8）
这种方法对于稀疏数据（即存在多个高度为0的小矩阵）还行，稠密的就没什么用处了。
具体就是用is_数据记录都有哪些格子是哪些高度，同类型高度有几个。比如样例，我就应该记录成
316523
从下往上，即
123356
放入is_ （类似一种数据结构的存储结构（我忘了。。。回头补）
1 1
2 4
3 2 0 5（这里表示有两个）
5 3
6 2
第一列表示给的数据“hi”，数据3后面的2表示高度3有两个，0和5与其他（第二列）数据一样，都是在n中的位置（以便最快给出，而不用遍历）
但感觉实现相当复杂，特别不好写，大概率写不出来。
思路2：
想到两次遍历n，n^2（10^6），1s绰绰有余。
实际写1：
有必要说一下，CCF貌似没有用 while(scanf("%d", &n) != EOF) 判断的写法，所以不要求重置赋值。也就是说我的代码对于CCF测评机是可以AC的，但是如果这样输入
9
9 9 9 9 9 9 9 9 9
81
3
3 2 1
81
发现第二组数据也是81了，CCF测评机类似手动不断运行一个一个测试一样，所以，为了一次输入多个样例最好，在while(scanf("%d", &n) != EOF) 下面加上这两句memset(map, 0, sizeof(map));
answer = 0;
实际写2：memset 需要 cstring
实际写3：
我用思路1写的时候(没写完最后是错的)，无意间我现本题后台数据“hi”高度并不只是10^4以内
错误代码不贴出来了，我就把本质发一下吧。
就是说，我把 is_[map[i]] = 1; 放到正确代码中会只得90分
代码
1 #include<cstdio>
2 #include<cstring>
3 int map[1050];
4 int is_[10050];//是否有此高度
5 int maxhigh;
6 int minhigh;
7 int main()
8 {
9 int n;
10 while(scanf("%d", &n) != EOF){
11 int answer = 0;
12 memset(map, 0, sizeof(map));
13 for(int i = 0; i < n; i ++)
14 {
15 scanf("%d", &map[i]);
16 is_[map[i]] = 1;
17 }
18 for(int i = 0; i < n; i ++){
19 int left = 0;
20 int right = 0;
21 int flag = i;
22 while(flag >= 0 && map[flag] >= map[i]){
23 if(flag != i)
24 left ++;
25 flag --;
26 }
27 flag = i;
28 while(flag < n && map[flag] >= map[i]){
29 if(flag != i)
30 right ++;
31 flag ++;
32 }
33 int thisS = (right + left + 1) * map[i];
34 if(thisS > answer)
35 answer = thisS;
36 }
37 printf("%d\n", answer);
38 }
39 }
重点就看加粗这句话，去掉就满分AC，加上就90，提示运行错误（即运行一般程序崩溃了，诸如除以0或者数组越界）
最后发现是数组越界，把int a[10050]，改成int a[30050]就好了。。。后台测试数据没有严格按照10000这个最高 hi 范围来。。。。。