84.柱状图中最大的矩形

链接：84.柱状图中最大的矩形
难度：Hard
标签：栈、数组、单调栈
简介：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

题解 1 - typescript

• 编辑时间：2020-05-30
• 执行用时：1300ms
• 内存消耗：35.8MB
• 编程语言：typescript
• 解法介绍：暴力循环。

var largestRectangleArea = function (heights: number[]): number {
  const len = heights.length;
  if (len === 0) return 0;
  let max = 0;
  for (let i = 0; i < len; i++) max = Math.max(getR(i), max);
  return max;
  function getR(i: number): number {
    const num = heights[i];
    let max = num;
    let w = 1;
    let low = num;
    let temp = num;
    while (temp >= 0 && i >= 1) {
      temp = (low = Math.min(heights[--i], low)) * ++w;
      max = Math.max(temp, max);
    }
    return max;
  }
};

题解 2 - typescript

• 编辑时间：2021-07-19
• 执行用时：104ms
• 内存消耗：49MB
• 编程语言：typescript
• 解法介绍：单调栈，获取两边比当前小的值。

function largestRectangleArea(heights: number[]): number {
  const len = heights.length;
  const left = new Array(len).fill(-1);
  const right = new Array(len).fill(len);
  const stack: number[] = [];
  let ans = 0;
  for (let i = 0; i < len; i++) {
    const h = heights[i];
    while (stack.length && heights[stack[stack.length - 1]] >= h) right[stack.pop()!] = i;
    if (stack.length) left[i] = stack[stack.length - 1];
    stack.push(i);
  }
  for (let i = 0; i < len; i++) ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
  return ans;
}