直方图中最大的矩形

问题概述

任务是找到直方图中可以形成的最大矩形区域。直方图中每个条形的宽度为 1，每个条形的高度由非负整数数组给出。

例如，给定高度数组 [2, 1, 5, 6, 2, 3]，直方图中最大的矩形面积为 10。

解决方法

使用基于堆栈的方法可以有效地解决该问题。这种方法涉及维护一个堆栈来跟踪直方图条形的索引，使我们能够在线性时间内计算最大矩形面积。以下是该算法的详细分解：

1. 初始化变量

• len：高度数组的长度。
• stack：用于存储直方图条形索引的空堆栈。
• max：一个变量，用于跟踪迄今为止找到的最大矩形区域。
• h：从堆栈中弹出的栏的高度。
• w: 高度为h形成的矩形的宽度。

2. 迭代 Heights 数组

我们从左到右迭代 heights 数组，并在数组末尾添加一个高度为 0 的最终虚拟条，以确保所有条都被处理。

迭代步骤：

• 压入当前柱的索引：对于每个柱，将其索引压入堆栈。然而，在此之前，我们需要确保当前的柱比存储在堆栈顶部的索引处的柱高。如果不是，我们从堆栈中弹出条，以使用弹出索引处的条作为最小条（即矩形的高度）来计算可以形成的矩形面积。

• 从堆栈中弹出并计算面积：

  • 从堆栈中弹出顶部索引。该索引表示矩形中最小条形的高度。
  • 计算矩形的宽度。如果弹出后堆栈为空，则意味着弹出的条是迄今为止最小的，并且其宽度从数组的开头延伸到当前索引。否则，宽度由当前索引与现在位于堆栈顶部的索引之间的距离减一确定。
  • 使用高度和宽度计算矩形的面积，如果该面积较大，则更新 max 变量。

3. 处理堆栈中剩余的条

迭代所有条形后，堆栈中可能仍留有一些条形。这些条的高度未经过处理，因为右侧没有较短的条。我们需要类似地处理这些剩余的条形，将它们从堆栈中弹出并计算面积。

代码详细解释

这是 JavaScript 代码，其中包含解释每个部分的注释：

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
  var len = heights.length;
  var stack = [];
  var max = 0;
  var h = 0;
  var w = 0;

  // Iterate through the heights array
  for (var i = 0; i <= len; i++) {
    // Ensure the loop processes the virtual bar with height 0 at the end
    while (stack.length && (i === len || heights[i] <= heights[stack[stack.length - 1]])) {
      // Pop the top index from the stack
      h = heights[stack.pop()];
      // Calculate the width of the rectangle
      w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      // Update the maximum area found so far
      max = Math.max(max, h * w);
    }
    // Push the current index onto the stack
    stack.push(i);
  }

  return max;
};

复杂性分析

• 时间复杂度： O(n)，其中 n 是直方图中的条形数量。每个条最多从堆栈中压入和弹出一次。
• 空间复杂度： 用于跟踪索引的堆栈的 O(n)。

以上是直方图中最大的矩形的详细内容。更多信息请关注PHP中文网其他相关文章！