算法训练营 Day 60 | ● 84.柱状图中最大的矩形

[KoEkko]

84.柱状图中最大的矩形

题目描述的是找能够勾勒出最大矩形的面积，我们可以找寻当前元素的左右两边第一个比他小的元素，表明以当前元素的高度，所能维持的最大长度是多少，最后直接相乘得到面积即可。

找第一个小，单调栈的顺序要求是从栈顶到栈底是递减的，所以会有以下两种特殊情况：

• 原始数组是递增的

这个情况，我们去遍历数组加入单调栈的时候，不会走到while循环里面的逻辑

• 第一个元素的右边就是比他小

这种情况，在计算left的时候会出现数组越界的情况，没有值。

为了避免这两种情况的发生，我们需要在数组首尾都添加0，这样子做，就能避免无法进入逻辑和第一个元素数组越界的情况。
（第二种情况也可以如果stack的长度小于0了，就取-1，因为最终我们都是取最大值的。res已经初始化为0了）

function largestRectangleArea(heights: number[]):number {
  heights.push(0); // 是防止数组是递增的，不会进入单调栈的逻辑
  const length = heights.length;
  const stack: number[] = [];
  stack.push(0);
  let res = 0;
  for(let i = 1; i < length; i ++) {
    let top = stack[stack.length - 1];
    while(stack.length && heights[i] < heights[top]) {
      const mid = stack.pop()!;
      const left = stack.length > 0 ? stack[stack.length - 1] : -1;
      const right = i;
      const w = right - left - 1;
      const h = heights[mid];
      res = Math.max(res, w * h);
      top = stack[stack.length - 1];
    }
    stack.push(i);
  }
  return res;
}