📑 题目：84. 柱状图中最大的矩形

🚀 本题 LeetCode 传送门

题目大意

给出每个直方图的高度，要求在这些直方图之中找到面积最大的矩形，输出矩形的面积。

解题思路

用单调栈依次保存直方图的高度下标，一旦出现高度比栈顶元素小的情况就取出栈顶元素，单独计算一下这个栈顶元素的矩形的高度。然后停在这里(外层循环中的 i–，再 ++，就相当于停在这里了)，继续取出当前最大栈顶的前一个元素，即连续弹出 2 个最大的，以稍小的一个作为矩形的边，宽就是 2 计算面积…………如果停在这里的下标代表的高度一直比栈里面的元素小，就一直弹出，取出最后一个比当前下标大的高度作为矩形的边。宽就是最后一个比当前下标大的高度和当前下标 i 的差值。计算出面积以后不断的更新 maxArea 即可。

代码

package leetcode
func largestRectangleArea(heights []int) int {
 maxArea := 0
 n := len(heights) + 2
 // Add a sentry at the beginning and the end
 getHeight := func(i int) int {
  if i == 0 || n-1 == i {
   return 0
  }
  return heights[i-1]
 }
 st := make([]int, 0, n/2)
 for i := 0; i < n; i++ {
  for len(st) > 0 && getHeight(st[len(st)-1]) > getHeight(i) {
   // pop stack
   idx := st[len(st)-1]
   st = st[:len(st)-1]
   maxArea = max(maxArea, getHeight(idx)*(i-st[len(st)-1]-1))
  }
  // push stack
  st = append(st, i)
 }
 return maxArea
}
func max(a int, b int) int {
 if a > b {
  return a
 }
 return b
}