84. 柱状图中最大的矩形

方法一：枚举

思路：通过枚举的方式进行求解，可以从枚举宽和枚举高的角度来着手。

枚举宽

枚举宽，其实就是在固定宽的情况下去获取高度。矩形会由最左边的柱子和最右边的柱子去构成边界，因此这个固定的宽可通过枚举最左边的柱子和最右边的柱子来获取。值得注意的是，这个边界可以重叠，此时矩形仅由一个柱子构成。

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
  const size = heights.length;
  let result = 0;
  // 从最左边的柱子开始枚举
  for (let i = 0; i < size; left++) {
    let minHeight = Infinity 
    // 枚举最右边的柱子
    for (let j = left; j < size; j++) {
      // 获取最小高度
      minHeight = Math.min(minHeight, heights[j])
      // 获取面积
      const area = minHeight * (j - i + 1)
      // 获取最小面积
      result = Math.max(result, area)
    }
  }
  return result
}

枚举高

枚举高，其实就是在固定高的情况下去获取宽。当以某个柱子的高度作为矩形的高度，此时就应该以这个柱子为中心，去找这个矩形的边界。也就是说，根据这个固定的高度，来找最左边的柱子和最右边的柱子要构成这个固定高的矩形，那么最左边和最右边的柱子，一定不能比固定高矮。根据这个条件，就可以找到矩形的最左和最右的柱子。值得注意的是，最左边的柱子和最右边的柱子会有重叠的情况，这个时候仅有一个柱子来构成这个矩形。

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
  let result = 0;
  for (let i = 0; i < heights.length; i++) {
    // 矩形的高度
    const height = heights[i]
        // 最左侧柱子的索引    
    let left = i;
    // 最右侧柱子的索引
    let right = i;
    // 要确保最左侧柱子的索引必须大于 0，并且它的高度必须大于等于矩形的高度
    while (left - 1 >= 0 && heights[left - 1] >= height) {
      left--;
    }
    // 要确保最右侧柱子的索引必须小于柱子的元素个数，并且它的高度必须大于等于矩形的高度
    while (right + 1 < heights.length && heights[right + 1] >= height) {
      right++;
    }
    // 求面积
    result = Math.max(result, height * (right - left + 1))
  }
  return result;;
};

方法二