如何在 C++ 中使用栈找到直方图中的最大矩形面积？

引言

要在C++中使用堆栈在直方图中找到最大的矩形面积，我们可以使用一种利用堆栈的特性来有效跟踪直方图条形索引的方法。这种方法确保我们只遍历直方图条形有限次数，从而优化了计算过程。

主要思想是使用堆栈存储直方图条形的索引，以保持递增高度的顺序。当我们遍历直方图时，我们执行以下步骤，如下所示：

1. 压入堆栈：当当前条形的高度大于或等于堆栈顶部存储的索引处的条形高度时，我们将当前索引压入堆栈。
2. 从堆栈弹出并计算面积：当我们遇到一个比堆栈顶部条形矮的条形时，这意味着我们已经到达了矩形宽度的末端。之后，我们从堆栈中弹出，将弹出的索引视为矩形的高度，并根据当前索引与新堆栈顶部索引之间的差值来计算宽度。

方法 1：简单方法

实施

输出

 
Maximum rectangular Area is 12   

说明

初始化结构

• 首先创建一个空堆栈来存储直方图条形的索引。
• 初始化一个变量来跟踪找到的最大面积，初始值设为零。

遍历直方图

• 开始从第一个条形到最后一个条形遍历直方图。

处理递增高度

• 对于直方图中的每个条形，如果堆栈为空，或者当前条形的高度大于或等于堆栈顶部的索引处的条形高度，则将当前索引压入堆栈。这意味着我们正在构建一个递增条形高度的序列。

在高度递减时计算面积

• 如果当前条形比堆栈顶部的索引处的条形矮，则表示递增高度序列的结束。
• 从堆栈中弹出顶部索引，并将其视为矩形的高度。
• 计算此矩形的宽度
• 如果堆栈现在为空，则宽度从开始到当前索引。
• 如果堆栈不为空，则宽度是当前索引与新堆栈顶部索引之间的差值减一（因为新堆栈顶部索引表示下一个矩形的开始）。
• 使用弹出的高度和计算出的宽度计算矩形的面积。
• 如果新计算出的面积更大，则更新最大面积。

继续遍历

• 继续此过程，直到到达直方图的末尾，直到遇到更矮的条形为止，一直压入索引并计算面积。

处理剩余索引

• 遍历完成后，堆栈中可能仍然有一些索引。这些索引代表直到最后都属于递增序列的条形。
• 从堆栈中弹出每个剩余索引，并按照前面所述计算面积。这确保了所有潜在的矩形都被考虑在内。

输出最大面积

• 最后，最大面积变量将保存在此过程中找到的最大的矩形面积。

让我们来看一个例子以更好地理解

考虑直方图 [6, 2, 5, 4, 5, 1, 6]：

从空堆栈和最大面积0开始。

遍历每个条形

• 对于 6：堆栈为空，压入索引 0。
• 对于 2：2小于6，弹出0，计算面积 6x1=6，将最大面积更新为6，压入索引 1。
• 对于 5：压入索引 2。
• 对于 4：4小于5，弹出2，计算面积 5x1=5，最大面积仍为6，压入索引 3。
• 对于 5：压入索引 4。
• 对于 1：1小于5，弹出4，计算面积 5x1=5，最大面积仍为6。然后弹出3，计算面积 4x3=12，将最大面积更新为12。压入索引 5。
• 对于 6：压入索引 6。

处理剩余索引

• 弹出6，计算面积 6x1=6，最大面积仍为12。
• 弹出5，计算面积 1x7=7，最大面积仍为12。

因此，最大的矩形面积是12。

复杂度分析

时间复杂度

算法的时间复杂度为 O(n)，其中 n 是直方图中条形的数量。

单次遍历：算法从左到右对直方图条形进行一次遍历。

压入和弹出操作：每个索引都只被压入堆栈一次，并从堆栈中弹出一次。由于每次压入和弹出操作都需要恒定的时间，因此操作的总数与条形数量成线性关系。

因此，总时间复杂度为 O(n)。

空间复杂度

算法的空间复杂度为 O(n)。以下是详细说明：

堆栈存储：在最坏的情况下，如果所有条形都按递增顺序排列，那么每个条形的索引都会被压入堆栈，这意味着堆栈将包含 n 个索引。

附加变量：附加变量（例如 max_area、i、tp、area_with_top）使用的空间是恒定的，不依赖于输入大小。

因此，总空间复杂度为 O(n)。

方法二：使用分治法

这种方法受到了用于查找最大子数组和的算法的启发，它涉及将直方图划分为更小的子问题并递归地求解每个问题。

实施

输出

 
Maximum rectangular Area is 12   

说明

步骤 1：问题定义

假设你有一个直方图，它由一个条形高度数组表示。你的目标是确定可以在这些条形中形成的最大的矩形面积。

步骤 2：基本情况

最简单的情况是直方图为空，或者你正在检查一个没有条形的范围。在这种情况下，最大的矩形面积为零。

步骤 3：查找最小条形

对于直方图中的任何给定条形范围，识别高度最小的条形。这个条形至关重要，因为：

• 它限制了跨越整个范围的任何矩形的高度。
• 它自然地将直方图分成两个更小的子直方图：一个在此条形的左侧，一个在此条形的右侧。

步骤 4：递归求解子问题

一旦找到了划分直方图的最小条形：

左子直方图：考虑最小条形左侧的条形。递归确定在此左侧部分中可以形成的最大的矩形面积。

右子直方图：同样，考虑最小条形右侧的条形。递归查找此右侧部分的最大的矩形面积。

步骤 5：合并结果

要找到当前范围的整体最大矩形面积：

• 跨越最小条形的面积：计算包含最小条形并跨越当前范围整个宽度的矩形的面积。该面积就是最小条形的高度乘以当前范围内条形的数量。
• 所有面积的最大值：比较获得的三个面积
• 左子直方图中的最大面积。
• 右子直方图中的最大面积。
• 跨越最小条形的面积。

这三个面积中的最大值是当前条形范围的答案。

步骤 6：递归方法

对于通过查找最小条形创建的每个子直方图，重复上述步骤，直到处理完所有可能的子直方图。

示例

让我们将此方法应用于示例直方图 [6, 2, 5, 4, 5, 1, 6]。

初始直方图：从整个条形范围开始。

查找最小条形：范围内的最小条形是索引 5 处的 1。

分而治之

• 左子直方图：条形 [6, 2, 5, 4, 5]
• 最小条形是索引 1 处的 2。
• 进一步划分为 [6] 和 [5, 4, 5]。
• 右子直方图：条形 [6]

计算面积

左侧部分：[6] 的最大面积为 6，[5, 4, 5] 的最大面积为 9。

右侧部分：[6] 的最大面积为 6。

跨越最小条形的面积：跨越最小条形 1 的面积为 7（高度 1 * 宽度 7）。

这些面积中的最大值是左子直方图 [5, 4, 5] 的 12。

复杂度分析

时间复杂度

用于在直方图中查找最大矩形面积的分治法的复杂度可能会因直方图的结构而异。

查找最小条形：每次在子直方图中查找最小条形时，对于整个直方图需要 O(n) 时间，划分后的一侧需要 O(n-1) 时间，依此类推。

递归划分：每次划分都会创建两个新的子问题。在最坏的情况下，如果直方图已经按递增或递减顺序排序，我们可能会进行 n 次递归调用，每次调用都需要 O(n) 时间。

在最坏的情况下，时间复杂度为

O(n)+O(n-1)+O(n-2)+…+O(1)=O(n2)

因此，最坏情况下的时间复杂度为 O(n2)。

空间复杂度

空间复杂度主要由分治法的递归堆栈决定。

递归调用：在最坏的情况下，如果直方图的划分方式使得每个子问题只减少一个元素，那么递归堆栈的深度最多可能为 n。

附加变量：函数中使用的其他变量（例如，用于存储最小索引和计算出的面积）使用恒定空间，不随输入大小缩放。

方法三：使用动态规划法

此方法涉及预先计算每个条形结束的最大矩形的宽度，然后使用这些宽度来查找最大面积。

实施

输出

 
Maximum rectangular Area is 12   

说明

步骤 1：理解问题

你有一个由高度数组表示的直方图，其中数组中的每个元素对应于直方图中条形的高度。目标是确定可以在这些条形中形成的最大的矩形面积。

步骤 2：初始设置

为了有效地查找最大的矩形面积，我们将使用两个数组 left 和 right 来存储每个条形的边界。这些边界将帮助我们确定以每个条形作为最短条形可以形成的最大的矩形的宽度。

步骤 3：查找左边界

对于直方图中的每个条形，我们需要找到其左侧最近的更矮的条形。这有助于我们理解当前条形在保持矩形高度的同时可以向左延伸多远。

• 从左到右遍历：从第一个条形开始，向最后一个条形移动。
• 使用堆栈：维护一个堆栈以跟踪高度递增的条形索引。
• 更新左数组：对于每个条形，从堆栈中弹出元素，直到找到一个比当前条形矮的条形。然后，当前条形的左边界是堆栈顶部元素的索引（如果堆栈不为空）。如果堆栈为空，则表示左侧没有更矮的条形，因此相应地设置左边界。

步骤 4：查找右边界

对于每个条形，我们还需要找到其右侧最近的更矮的条形。这有助于我们理解当前条形在保持矩形高度的同时可以向右延伸多远。

• 从右到左遍历：从最后一个条形开始，向第一个条形移动。
• 使用堆栈：重用堆栈来跟踪高度递增的条形索引。
• 更新右数组：对于每个条形，从堆栈中弹出元素，直到找到一个比当前条形矮的条形。然后，当前条形的右边界是堆栈顶部元素的索引（如果堆栈不为空）。如果堆栈为空，则表示右侧没有更矮的条形，因此相应地设置正确的边界。

步骤 5：计算最大面积

确定了每个条形的左侧和右侧边界后，我们现在可以计算每个条形的最大矩形面积，并跟踪整体最大面积。

• 确定宽度：对于每个条形，包含该条形的最大矩形的宽度计算为右边界与左边界之差减一。
• 计算面积：然后，面积是条形的高度乘以该宽度。

更新最大面积：将此面积与迄今为止找到的最大面积进行比较，并相应地进行更新。

示例

考虑一个高度为 [6, 2, 5, 4, 5, 1, 6] 的直方图

左边界计算

• 对于条形 6（索引 0）：左侧没有条形，因此左边界为 -1。
• 对于条形 2（索引 1）：左侧没有更矮的条形，因此左边界为 -1。
• 对于条形 5（索引 2）：条形 2 是左侧最近的更矮条形，因此左边界为 1。
• 对于条形 4（索引 3）：条形 2 是左侧最近的更矮条形，因此左边界为 1。
• 对于条形 5（索引 4）：条形 4 是左侧最近的更矮条形，因此左边界为 3。
• 对于条形 1（索引 5）：左侧没有更矮的条形，因此左边界为 -1。
• 对于条形 6（索引 6）：条形 1 是左侧最近的更矮条形，因此左边界为 5。

右边界计算

• 对于条形 6（索引 6）：右侧没有条形，因此右边界为 7。
• 对于条形 1（索引 5）：右侧没有更矮的条形，因此右边界为 7。
• 对于条形 5（索引 4）：条形 1 是右侧最近的更矮条形，因此右边界为 5。
• 对于条形 4（索引 3）：条形 1 是右侧最近的更矮条形，因此右边界为 5。
• 对于条形 5（索引 2）：条形 4 是右侧最近的更矮条形，因此右边界为 3。
• 对于条形 2（索引 1）：条形 1 是右侧最近的更矮条形，因此右边界为 5。
• 对于条形 6（索引 0）：条形 2 是右侧最近的更矮条形，因此右边界为 1。

面积计算

• 对于条形 6（索引 0）：宽度为 1，面积为 6*1=6。
• 对于条形 2（索引 1）：宽度为 5，面积为 2*5=10。
• 对于条形 5（索引 2）：宽度为 1，面积为 5*1=5。
• 对于条形 4（索引 3）：宽度为 3，面积为 4*3=12。
• 对于条形 5（索引 4）：宽度为 1，面积为 5*1=5。
• 对于条形 1（索引 5）：宽度为 7，面积为 1*7=7。
• 对于条形 6（索引 6）：宽度为 1，面积为 6*1=6。

找到的最大面积是 12。

复杂度分析

时间复杂度

总体时间复杂度： O(n)

左边界计算： O(n)，因为每个条形都会被压入和弹出堆栈一次。

右边界计算： O(n)，原因相同。

面积计算： O(n)，因为它涉及对条形的单次遍历。

空间复杂度

总体空间复杂度： O(n)

辅助数组： O(n) 用于 left 和 right 数组。

堆栈：最坏情况下为 O(n)，此时堆栈可以容纳所有条形索引。

因此，动态规划方法的时​​间复杂度为 O(n)，空间复杂度为 O(n)。