正文

揭秘单调栈如何轻松计算最大面积矩形

/0 浏览量
0401

单调栈是一种在解决一些算法问题时非常有效的数据结构。它可以帮助我们高效地处理一系列的序列或数据，比如在计算最大面积矩形时。下面，我将详细地介绍单调栈的原理，并通过一个具体的例子来展示如何使用单调栈轻松计算最大面积矩形。

单调栈的基本原理

单调栈是一种特殊的栈，它保证了栈中的元素是单调的，即要么始终递增，要么始终递减。在单调递增栈中，每次我们添加一个元素时，都会检查它是否大于栈顶元素；在单调递减栈中，则检查它是否小于栈顶元素。

单调栈的几个关键操作包括：

  • push(int x)：将元素 x 压入栈中。
  • pop()：从栈中弹出元素。
  • peek()：查看栈顶元素，但不弹出。
  • isEmpty()：检查栈是否为空。

最大面积矩形的背景

假设我们有一个由 ‘(’ 和 ‘)’ 组成的字符串，我们需要计算在这个字符串中可以形成的最大面积矩形的面积。

例如，对于字符串 "(())()`，我们可以形成以下矩形：

()
()(())

第一个矩形的面积是 1，第二个矩形的面积是 4，因此最大面积矩形的面积是 4。

使用单调栈计算最大面积矩形

要计算最大面积矩形，我们可以使用单调递增栈来处理字符串中的 ‘(’ 和 ‘)‘。

  1. 处理 ‘(‘： 当我们遇到 ‘(’ 时，将其压入栈中。
  2. 处理 ‘)‘： 当我们遇到 ‘)’ 时，从栈中弹出元素，直到遇到 ‘(‘。计算弹出元素和当前 ‘)’ 之间的矩形面积，并与当前已知最大面积进行比较。

以下是具体的步骤：

  1. 创建一个单调递增栈。
  2. 遍历字符串中的每个字符：
    • 如果是 ‘(‘，将其索引压入栈中。
    • 如果是 ‘)‘，弹出栈顶元素，直到栈顶元素是 ‘(‘。计算弹出的 ‘(’ 和当前 ‘)’ 之间的矩形面积。
  3. 对于栈中剩余的 ‘(‘，将它们的索引和字符串末尾的索引组合，计算面积。

代码示例

以下是用 Python 实现的代码示例：

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # 为了处理栈中剩余的 '('
    
    for i, h in enumerate(heights):
        start = i
        while stack and heights[stack[-1]] > h:
            start = stack.pop()
        width = i - start
        max_area = max(max_area, width * heights[start])
        stack.append(i)
    
    return max_area

# 示例
print(largestRectangleArea([2, 1, 2, 4, 3, 3]))

在这个例子中，largestRectangleArea 函数接收一个整数列表 heights，它表示矩形的高。函数计算并返回最大面积矩形的面积。

通过单调栈，我们可以轻松地计算出最大面积矩形，而不需要遍历整个字符串来计算每个可能的矩形的面积。这种方法的时间复杂度是 O(n)，其中 n 是字符串的长度，这使得它在处理大量数据时非常高效。

-- 展开阅读全文 --