简单来讲单调栈就是里面所有值都是单调递增或者递减的栈，这里先拿递增来举例说明，下面是一个典型的单调递增栈的模板：
for(int i = 0; i < A.size(); i++){
while(!in_stk.empty() && in_stk.top() > A[i]){
in_stk.pop();
}
in_stk.push(A[i]);
}
这种数据结构能干什么呢？想象下如果有一个数组， [3, 7, 8, 4]，要在 O(N) 的时间内找到每个元素前面或者后面的最小值该怎么去做？这就是单调栈的作用
-
找到元素前面的最小值，
PLE(Previous Less Element)。以上面的数组为例：
7 的 PLE 为 3，
8 的 PLE 为 7，
4 的 PLE 为 3，
如果我们不直接把值塞进去，而是把数组下表扔进栈，那么我们就可以获取到一个新的 PLE 数组。如下：
// previous_less[i] = j means A[j] is the previous less element of A[i].
// previous_less[i] = -1 means there is no previous less element of A[i].
vector<int> previous_less(A.size(), -1);
for(int i = 0; i < A.size(); i++){
while(!in_stk.empty() && A[in_stk.top()] > A[i]){
in_stk.pop();
}
previous_less[i] = in_stk.empty()? -1: in_stk.top();
in_stk.push(i);
}
- 找到元素后面的最小值，
NLE(Next Less Element)
同理可以获取到下面的模板
// next_less[i] = j means A[j] is the next less element of A[i].
// next_less[i] = -1 means there is no next less element of A[i].
vector<int> next_less(A.size(), -1);
for(int i = 0; i < A.size(); i++){
while(!in_stk.empty() && A[in_stk.top()] > A[i]){
auto x = in_stk.top();
in_stk.pop();
next_less[x] = i;
}
in_stk.push(i);
}
子数组的最小值之和：给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。
利用上述方法求出某个元素距离 PLE 和 NLE 之间的距离，然后对 A[i]*left[i]*right[i] 进行累加。
func sumSubarrayMins(A []int) int {
mod := int(1e9+7)
stack := make([]int, 0, len(A))
left, right := make([]int, len(A)), make([]int, len(A))
// 初始化 防止最小值没有处理的情况
for i := 0; i < len(A); i += 1 {
left[i] = i + 1
right[i] = len(A)-i
}
for i := 0; i < len(A); i += 1 {
for len(stack) != 0 && A[stack[len(stack)-1]] > A[i] {
last := stack[len(stack)-1]
right[last] = i - last
stack = stack[:len(stack)-1]
}
if len(stack) != 0 {
left[i] = i - stack[len(stack)-1]
}
stack = append(stack, i)
}
// 累加
var sum int
for i := 0; i < len(A); i += 1 {
sum = (sum + A[i]*left[i]*right[i]) % mod
}
return sum
}下一个更大元素 II:给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
这是一个很基础的单调递减栈，主要的问题在于这个是一个循环数组，所以需要遍历两次，第二次遍历的时候不再入栈.
func nextGreaterElements(nums []int) []int {
if len(nums) == 0 {
return nil
}
stack, ret := make([]int, 0, len(nums)), make([]int, len(nums))
// 第一遍遍历初始化
for i := range ret {
ret[i] = -1
}
// 这里会遍历两遍，只有第一次遍历的时候数据才会入栈
for i := 0; i < len(nums) * 2; i += 1 {
i := i % len(nums)
for len(stack) != 0 && nums[stack[len(stack)-1]] < nums[i] {
ret[stack[len(stack)-1]] = nums[i]
stack = stack[:len(stack)-1]
}
if i < len(nums) {
stack = append(stack, i)
}
}
return ret
}largest-rectangle-in-histogram
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积
在栈的练习中已经出现过了