最大的矩形纸片 时间限制: 1000MS 内存限制: 65536KB 题目描述: 编程实现:最大的矩形纸片 一张半边参差不齐的网格纸 (网格边长均为1)，有一边是完整没有破损的。现要从中剪出一片面积最大的矩形纸片。 给定网格纸中完整边的长度N (1<=N<=1000000) ，以及网格中每一列残存部分的高度(1<=高度<=10000)，输出能够剪出的最大矩形纸片面积。 例如: N=6，每一列残存部分的高度依次为3、2、1、4、5、2，如下图所示： 可以发现，沿着红色框可以剪出的矩形纸片面积最大，为8，所以输出8。 输入描述 第一行输入一个正整数N（1≤N≤1000000），表示纸片完整边的长度 第二行输入N个正整数（1≤正整数≤10000），表示每列格子残存部分的高度，两个正整数之间用一个空格隔开 输出描述 输出一个正整数，表示能够剪出的最大矩形纸片面积 【样例输入】 6 3 2 1 4 5 2 【样例输出】 8

答案解析

评分标准：

6分：能正确输出第一组数据；

6分：能正确输出第二组数据；

6分：能正确输出第三组数据；

6分：能正确输出第四组数据；

6分：能正确输出第五组数据；

6分：能正确输出第六组数据；

6分：能正确输出第七组数据；

6分：能正确输出第八组数据；

6分：能正确输出第九组数据；

6分：能正确输出第十组数据。

【解析】

本题为经典问题，改编自LeetCode 84。由题意，不难想到枚举矩形的左右两条竖边的位置，则矩形的高度为这段位置上每列高度的最小值。考虑到在枚举竖边位置的双重循环中，右边竖边每次循环向右移动时，可以顺带维护整段的列高度最小值，因此可以实现以下的O(n2) 程序，足以拿到相当高的部分分，但对于本题n ≤ 106 的极限数据还无能为力。

注意对于n = 106，且每列高度都为10000 的情形下，答案恰好为1010，已经超过了C++int 类型可表示的最大值。因此答案需要使用long long 类型存储。

本题的满分做法需要用到单调栈，这是提高级才涉及的知识点。

考虑以第i 列为所求矩形中高度最低列的情形，记：

• 第i 列的高度为a[i]；

• 从第i 列出发向左，包括第i 列在内，高度不少于第i 列高度a[i] 的列的数量为l[i]；

• 从第i 列出发向右，包括第i 列在内，高度不少于第i 列高度a[i] 的列的数量为r[i]；

则此时矩形面积最大为：a[i] × (l[i] + r[i] − 1)；答案即求i = 1, 2, . . . , n 时，算式的最大值。

现考虑高效计算l[i]，r[i]。

对第i 列，若要暴力计算l[i]，只能从第i 项向左遍历至第一个高度严格小于a[i] 的位置。但既然遍历时只考虑高度严格小于a[i] 的位置，我们可以考虑用一个数据结构，保存下高度严格小于当前a[i] 的位置。这一数据结构要满足以下要求：

• 对第i 列，只需要求从它开始向左的第一个严格小于a[i] 的位置，那么这一待求位置要能够在数据结构中较方便地暴露出来。

• 遍历时，当前循环考虑的第i 列，在日后的遍历中可能成为对于后面列而言较“矮”的一列，因此第i 列要在循环结束前加入数据结构中。

向左找到的位置在遍历中是靠后加入数据结构的，而它作为比较“矮”的一列又要靠前先给出，因此栈就是处理这一问题的最佳人选。具体维护过程如下：

• 循环开始时，如果栈顶的列编号对应的高度a[s.top()] 不少于当前列的高度a[i]，则将栈顶元素，反复执行直至不满足上述条件：要么栈为空，要么栈顶对应的列的高度已经严格小于a[i]。

• 循环快结束时，将当前列的编号i 压入栈顶。

注意：在程序执行过程中，栈保存的并不是第i 列之前所有高度不足a[i] 的列编号。以三列高度为3 2 3 的情形为例，遍历到最后一个3 时，栈中的编号元素从底至顶依次为：2、3。实际上第一个3 的编号1 没有必要压入栈中，可以分类讨论两种情形：

1. 如果后续入栈的列编号对应高度a[i] 严格大于2，栈的弹出会在中间的第2 列停下，无需前面的第1 列；

2. 如果对应高度不足2，那么哪怕之前把第1 列压入了栈中，也会因为第1 列高度比第2 列还高而一并出栈，起不到作用。

按照上述操作，可以发现：每时每刻栈中编号元素从底至顶对应的高度是单调递增的，因而称作单调栈。下图给出了题目样例数据对应的单调栈变化情况。

由对称性，r[i] 也可以类似地求出。上述过程中，每个下标i 至多会入栈一次，出栈一次，因此单调栈预处理计算l[i]，r[i] 和最后统计答案都是O(n) 的，足以通过本题。

实现代码时，栈可能出现反复弹出至空的情况，此时再调用s.top() 方法会导致程序崩溃，因此可以考虑给栈中加入兜底的“哨兵”元素。