求解直方图中最大矩形面积的问题

"直方图中最大的矩形问题的算法解析及C++实现" 直方图中最大的矩形问题是计算机科学中常见的算法问题，通常出现在数据结构和算法的面试或竞赛中。这个问题要求在一组宽度相同、高度各异的矩形（直方图）中找到面积最大的矩形。这个矩形必须与直方图的基线对齐，即其宽度沿直方图的宽度方向延伸。 ## 题目描述 给定一个直方图，其中每个矩形的宽度为1，高度不同。任务是找到这个直方图中能够覆盖的最大的矩形面积。直方图可以用一系列整数表示，每个整数代表一个矩形的高度。例如，序列`2,1,4,5,1,3,3`描述了一个直方图，其中每个数字对应一个高度。 ## 输入格式 输入以整数`n`开始，表示直方图中矩形的数量。接下来的`n`个整数`h1, h2, ..., hn`描述了直方图中每个矩形的高度。 ## 输出格式 输出一个整数，表示直方图中最大的矩形面积。 ## 数据范围 - `1 ≤ n ≤ 100000` - `0 ≤ hi ≤ 1000000000` ## 示例 输入： ``` 7 2 1 4 5 1 3 3 0 ``` 输出： ``` 8 4000 ``` 第一个例子中，最大的矩形面积为8，第二个例子中，没有矩形，所以面积为0。 ## 参考答案 这个问题可以通过栈来解决，使用两个数组`l`和`r`来记录每个矩形可以向左右两侧扩展的边界。这里使用了两个辅助数组`h`和`q`，`h`用于存储输入的高度，`q`用于存储栈的状态。 1. 初始化栈`q`，并将`h[0]`和`h[n+1]`设置为负无穷大，以便于边界处理。 2. 遍历直方图，每次遇到一个高度小于栈顶元素高度的矩形，就将栈顶元素及其对应的`l`值更新到当前索引`i`，并弹出栈顶元素，直到栈为空或栈顶元素高度小于等于`i`处的矩形高度。 3. 将当前索引`i`压入栈`q`，并将`l[i]`值更新。 4. 重复步骤2和3，直到遍历完所有矩形。 5. 使用类似的方法，通过维护一个右边界数组`r`，记录每个矩形可以向右扩展的边界。 6. 在遍历过程中，可以实时计算每个矩形的面积（`height * (r[i] - l[i] + 1)`），并记录最大面积。 ```cpp #include<iostream> #include<algorithm> using namespace std; const int N = 100010; int h[N], l[N], r[N], q[N]; int main() { int n; while (scanf("%d", &n), n) { for (int i = 1; i <= n; i++) scanf("%d", &h[i]); h[0] = h[n + 1] = -1; int tt = -1; q[++tt] = 0; for (int i = 1; i <= n; i++) { while (h[q[tt]] >= h[i]) tt--; l[i] = i - q[tt]; q[++tt] = i; } tt = -1; // 初始化右边界数组 for (int i = n; i >= 1; i--) { while (h[q[tt]] > h[i]) tt--; r[i] = q[tt + 1]; } int max_area = 0; for (int i = 1; i <= n; i++) { max_area = max(max_area, h[i] * (r[i] - l[i] + 1)); } printf("%d\n", max_area); } return 0; } ``` 这段代码中，首先初始化了栈`q`和边界数组`l`，然后遍历直方图计算左边界。接着，反向遍历计算右边界。最后，遍历一次直方图计算每个矩形的面积，并更新最大面积。 通过这种方法，我们可以有效地在O(n)的时间复杂度内找到直方图中最大的矩形面积，空间复杂度为O(n)。这种算法利用了栈的数据结构特性，有效地解决了直方图最大矩形问题。