刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=10^5
• 0 <= heights[i] <= 10^4

思路

其实这个问题跟接雨水很相近，我的思路都是

对于每个高度都有对应的左右边界，可以求得此高度下的最大矩形面积

那么我们的思路就转变成了求得每个高度的左右边界

单调栈

在我们运用单调栈思路，从左到右遍历元素时

可以将比 当前元素对应高度 高的元素都弹出，这样就很容易求得 当前元素对应高度 的 左边界

• 如下图 (图一) 示例，此时弹出 位置0 后，栈内没有其他元素了，当前元素 位置1 的 左边界 也就是初始化值 -1
  

• 如下图 (图二) 示例，如果此时栈内还有其他元素，那么 当前元素 位置2 的 左边界 就是剩下元素中的 栈顶元素 位置1
  

并且在 栈顶元素 弹出栈时， 当前元素 其实也正是 栈顶元素 的 右边界

• 同样如 (图一) 示例，此时将要出栈的 栈顶元素 位置0，他的 右边界 也就正是 即将入栈的 当前元素 位置1

思路大体就是这样了，细节在注释～

代码

func largestRectangleArea(heights []int) int {
	n := len(heights)
	// 对于每个高度来说，找到能不低于当前高度的左右边界时，就可以求的此高度下的最大面积了
	// 初始化左右边界数据
	left := make([]int, n)
	right := make([]int, n)
	// 初始化左右边界数据，当数据在 heights数组中 最终找不到边界时，初始化值就是其左右边界
	for i := 0; i < n; i++ {
		left[i] = -1
		right[i] = n
	}

	pointStack := []int{}
	for i := 0; i < n; i++ {
		// 如果 栈顶元素对应高度 大于 当前元素对应高度，那么 当前元素 就是 栈顶元素 的右边界
		// 参考图一
		for len(pointStack) > 0 && heights[i] <= heights[pointStack[len(pointStack)-1]] {
			right[pointStack[len(pointStack)-1]] = i
			pointStack = pointStack[:len(pointStack)-1]
		}
		// 弹出完毕后 栈顶元素对应高度 小于 当前元素对应高度，那么 栈顶元素 就是 当前元素 的左边界
		// 参考图一、图二
        // 这里因为已经在初始化里写入了 -1，所以图一的 左边界 情况没有具体的代码体现
		if len(pointStack) > 0 {
			left[i] = pointStack[len(pointStack)-1]
		}
		// 当前元素 处理完毕，入栈处理下一个元素
		pointStack = append(pointStack, i)
	}
	res := 0
	for i := 0; i < n; i++ {
		// 底边长 不包含左右边界本身，所以需要 再减1
		res = max(res, (right[i]-left[i]-1)*heights[i])
	}
	return res
}