单调栈

​ 单调栈是保持栈元素是有序的，如果破坏了单调性则出栈，直到满足栈的单调性。

​ 一般单调栈分为单调递增栈和单调递减栈。

​ 其主要解决：找到下一个比它大的元素或者比它小的元素

核心原理

当你入栈的时候，发现栈顶元素比你大，那么就让栈顶元素出栈，直到遇到比你小的元素，你再入栈。

从上面的原理你可以看出，单调递增栈可以找到下一个比它小的元素。

例子：

data = [1,3,5,1,2,3,6]

单调栈一般存储的内容是数据在原始数组中的具体位置，也就是索引。下面为了方便介绍单调栈的单调性，选择存储元素的具体值进行介绍。

• 第一步入栈 stack = [1]
• 判断3是否比栈顶元素小，如果小，则让栈顶元素出栈，让3进栈，如果比栈顶元素大，那么直接进栈就可以了 此时 stack=[1,3]
• 与第二步一样 此时stack=[1,3,5]
• 当1比5小的时候，5就找到了比它小的元素了，然后就可以处理具体的逻辑了 5出栈，然后继续判断1是否小于3，直到遇到不小于1的元素，1才入队 此时stack=[1,1]
• 之后2，3，5都比栈顶元素大，所以依次入队 此时stack=[1,1,2,3,6]
• 也就是说这些元素没有找到序列中比它小的元素。
• 在上面的逻辑中，我们发现单调栈处理数据时，数据每个元素的位置是固定的。

为什么单调栈一般存储的是元素的位置，而不是值呢？

主要原因是在数组中的元素的值是可重复的，但是索引是唯一的。

如果我们要计算下一个比它小的元素的距离时，我们只需要将该元素的索引 - 栈顶元素的索引就可以直接计算出距离了。

接下来我们使用具体的代码来解决相应的问题。

给定一个数组，然后找到每一个元素右边比它小的元素之间的距离。

package monotonicincreasingstack

func GetDistances(data []int) []int {
	n := len(data)
	if n == 0 {
		return []int{}
	}

	result := make([]int, len(data))

	stack := []int{}

	for i := 0; i < n; i++ {

		for len(stack) > 0 && data[stack[len(stack)-1]] /*栈顶元素*/ > data[i] {
			topIdx := stack[len(stack)-1]
			stack = stack[:len(stack)-1] //出栈
			result[topIdx] = i - topIdx
		}

		stack = append(stack, i)

	}

	return result
}

单调递减栈与单调递增栈逻辑基本上一致，只是在判断出队的时候，时采用栈顶元素小于当前元素的时候出栈。

解决下一个比它大的元素。

应用

1. 基础入门（下一个更大/更小元素）

这些题目是单调栈的模板题，适合用来熟悉“入栈、出栈、更新结果”的标准流程。

2. 进阶应用（贡献法与区间最值）

这类题目不再是简单的找邻居，而是利用单调栈确定的边界来计算面积、和或宽度。

3. 字符串与序列优化（贪心 + 单调栈）

这类题目通常要求我们在移除若干字符后，使得剩下的序列字典序最小或最大。

4. 树与表达式处理

单调栈有时也会出现在处理树结构或特定数学表达式中。