LeetCode热题（JS版） - 84. 柱状图中最大的矩形

题目

给定一个非负整数数组 heights，表示一个柱状图中各个柱子的高度。每个柱子的宽度为1。找到柱状图中面积最大的矩形。

示例

输入: [2,1,5,6,2,3] 
输出: 10 
解释: 上图所示的矩形即为面积最大的矩形，其面积为2x5 = 10。

思路

动态规划

首先，我们定义一个辅助数组dp，长度与柱状图相同。dp[i]表示以第i个柱子为右边界的最大矩形的宽度。

然后，我们从左到右遍历柱状图：

1. 如果当前柱子的高度小于等于前一个柱子的高度，说明当前柱子无法与前一个柱子组成更大的矩形，将dp[i]设为0。
2. 否则，找到从当前柱子向左延伸的最远位置left，使得从left到第i个柱子之间的所有柱子的高度都大于等于当前柱子的高度。此时，dp[i] = dp[left] + 1。

接下来，我们再次从左到右遍历柱状图，并记录每个柱子的最大矩形面积。对于每个柱子i，其最大矩形面积为：(dp[i] + 1) * height[i]，其中height[i]为当前柱子的高度。

最终，我们取所有柱子的最大矩形面积的最大值即可。

代码实现

function largestRectangleArea(heights: number[]): number {
  const n = heights.length;
  const dp: number[] = new Array(n).fill(0); // 辅助数组dp，记录以某个柱子为右边界的最大矩形宽度

  let maxArea = 0; // 最大矩形面积

  for (let i = 0; i < n; i++) {
    if (i > 0 && heights[i] <= heights[i - 1]) {
      // 如果当前柱子高度小于等于前一个柱子的高度，无法组成更大矩形，宽度设为0
      dp[i] = 0;
    } else {
      let left = i;
      while (left > 0 && heights[left - 1] >= heights[i]) {
        // 找到从当前柱子向左延伸的最远位置left，使得[left, i]范围内的柱子高度都大于等于当前柱子高度
        left--;
      }
      dp[i] = dp[left] + 1; // 计算当前柱子为右边界的最大矩形宽度
    }

    const area = dp[i] * heights[i]; // 计算当前柱子的最大矩形面积
    maxArea = Math.max(maxArea, area); // 更新最大矩形面积
  }

  return maxArea;
}

复杂度分析

时间复杂度为O(n)，空间复杂度为O(n)。

• 时间复杂度：在遍历柱状图的过程中，每个柱子都需要向左寻找最远位置，这一步的时间复杂度为O(n)，其中n是柱状图的长度。因此，整个算法的时间复杂度为O(n)。
• 空间复杂度：使用了一个辅助数组dp来记录以某个柱子为右边界的最大矩形宽度，所以额外的空间复杂度为O(n)，其中n是柱状图的长度。