单调栈模板总结
基本概念不再多说了。因为个人常常在细节上出错，所以总结一下单调栈的考虑点和写法。
ordered_stack.png
如上图求解最大面积，由遍历的思想，遍历每一个位置，以此位置为高的最大宽度应该是 左边界为向左小于点的位置后 和 右边界为向右小于此点的位置前 之间。即上图 B 作用的宽度为 (A, C) 之间（前开后开）。
A、C 分别为 B 作用范围取不到的左边界和右边界，为了方便下面的表述，下文就用 左边界 和 右边界 来表述。说法不严谨，但知道意思即可。
单调递增栈的解法流程
由上分析，所以我们需要找的是每一个点它的左右小于此值的位置。所以：
- 首先要明白一个前提，单调递增栈关键要存储的是 位置，通过原数组能拿到值；
- 单调递增栈因为递增，所以栈中每一个元素的左边界都是栈中的前一个元素；
- 上条中栈底位置的左边界要特殊处理
- 每一个栈外的元素可通过与栈顶元素进行比较，判断是否为栈顶元素的右边界（栈顶元素可以先弹出比较，也可以不弹出比较）
- 如果栈外元素 > 栈顶元素，此栈外元素入栈，进而维护了 单调递增栈
- 如果栈外元素 < 栈顶元素，即找到了栈顶元素的 右边界，即可以按左右边界计算作用面积
- 上步中弹出栈顶元素后，将栈外元素继续与栈顶元素比较，即跳转到 4，直到满足 5 中的条件，分析下一个栈外元素
- 直到所有栈外元素分析完，最后一个元素最终会入栈，最终只剩下栈中的元素还没有计算作用面积
- 依次弹出栈中元素，右边界为数组溢出位置的第一个下标，左边界为栈中前一个元素，计算作用面积
- 直到栈为空，即计算了所有位置的作用面积
由上流程，可以总结一下：
- 问题的关键在于如何找到一个元素它的左右边界
- 利用单调递增栈可以很容易找到某元素的左边界
- 通过栈外元素与栈顶的比较，能找到栈顶元素的右边界
- 注意上两条，可以得出，单调栈相关算法每次分析的元素是 栈顶元素
写代码注意问题
- 因为每次判断的是栈顶元素，所以栈顶要不要出栈，哪种方式编程最简单？
- 出栈后若栈非空则此时的栈顶元素为左边界
- 出栈后与栈外元素比较，若栈外元素大，需要将两个都放入栈中
- 出栈后若栈外元素小，则应该循环出栈，直到此栈外元素大于栈顶或栈空，入栈
- 栈底元素的左边界问题，数组最后一个元素的右边界问题
- 常见的逻辑会在循环完最后一个元素后，单独循环栈中的元素出栈，即两个主循环操作（其实第一个内部还有一个循环，总共三个）
- 如果在原数组最左边放一个最小值，最右边放一个最小值将不用再考虑第二个循环（但注意可行性，注意不要取溢出位置的数组元素）
- 判断栈顶与栈外元素的大小用大于还是大于等于（最后是 else）？
- 这个要看情况，如果数组中没重复元素则没问题
- 如果数组中有重复元素，但结果只求最大面积，那也没问题
- 如果数组中有重复元素，但要求每个位置对应的作用面积，则需要额外添加存储结构（思考下左边界和右边界就明白了）
模板
以 剑指 Offer II 039. 直方图最大矩形面积 为例，讲解规划此算法的策略。让其只用一个主循环逻辑（嵌套一个算两个了）。
主要策略：
- 栈底放一个 虚拟的边界 来解决所有节点的左边界的问题（虚拟边界 的取值靠封装取值函数保证取值安全，取值返回一个取不到的小值）
- 数组最外层也放一个 虚拟的边界 以保证栈中元素可以都弹出来
- 封装数组取值，覆盖虚拟边界取到比列表中最小值还小的值
第二条是去除单独的循环考虑弹出栈内元素的关键。
下方，虚拟节点
heights[-1]和height[len(height)-1]都设置为 -1，这样在代码 ① 位置注意不能取到=，否则可能不存在 peek，如果将 heights[-1] 设为 -2 的话，① 处的条件可以取到=。
func largestRectangleArea(heights []int) int {
stack := make([]int, 0, len(heights)) // 初始化栈
// 初始放入 虚拟边界 和 第一个下标（虚拟边界肯定小于任何下标的值）
stack = append(stack, -1, 0)
// 用安全的取值函数封装取数组的取值
getVal := func(i int ) int {
if i < 0 || i >= len(heights) {
return -1
}
return heights[i]
}
max := 0
for i := 1; i <= len(heights); i++ {
for { // 栈底有个占位的最小值，所以肯定有一个 pop 的值
var pop int
// 先 pop 出栈顶比较好，因为 peek 也可以通过栈顶元素获取
pop, stack = stack[len(stack)-1], stack[:len(stack)-1]
if getVal(pop) > getVal(i) { // ①
peak := stack[len(stack) - 1] // 注意 peek 要在条件内，因为此条件外不保证栈中一定有元素
if width := i - peak - 1; getVal(pop)*width > max {
max = getVal(pop) * width
}
} else if getVal(pop) < getVal(i){
stack = append(stack, pop)
break
} else { // equal
break // 因为引入了占位的值，所以需要考虑 equal 的情况
// 此种情况需要按题进行判断
}
}
stack = append(stack, i) // 放入元素
}
return max
}
