单调栈是一种特殊的栈结构，它的元素按照一定的顺序排列，通常是递增或者递减。单调栈在许多算法问题中都很有用，特别是在需要快速找到数组中某些元素的最小值或最大值的场景下。
单调栈的类型：
- 单调递增栈：栈中的元素按从栈底到栈顶的顺序递增，即栈顶元素总是大于等于栈内的其他元素。例如，如果有元素依次入栈是 [1, 2, 3]，则这是一个单调递增栈。
- 单调递减栈：栈中的元素按从栈底到栈顶的顺序递减，即栈顶元素总是小于等于栈内的其他元素。例如，如果有元素依次入栈是 [3, 2, 1]，则这是一个单调递减栈。
如何构建单调栈：
- 在遍历一个数组的过程中，我们不断将当前元素与栈顶元素比较：
- 单调递增栈：如果当前元素小于栈顶元素，我们就将栈顶元素弹出（即移除栈顶元素），因为此时我们发现了一个更小的元素，前面的更大元素已经没有继续留在栈中的必要了。
- 单调递减栈：如果当前元素大于栈顶元素，我们就将栈顶元素弹出（即移除栈顶元素），因为此时我们发现了一个更大的元素，前面的更小元素已经没有继续留在栈中的必要了。
单调栈的应用场景：
- 寻找每个元素的下一个更大/小元素：单调栈可以有效地找到数组中每个元素的下一个更大或更小的元素，这在需要快速查找这些信息的问题中非常有用。
- 移除K位数字问题：在这个问题中，我们使用单调递增栈，通过不断移除栈顶更大的数字来确保剩下的数字尽可能小。
示例：
假设我们有一个数组 [3, 2, 5, 1]，并且我们想要构建一个单调递增栈。
- 开始时栈为空。
- 处理
3：栈为空，直接入栈。栈[3]。 - 处理
2：当前元素2小于栈顶元素3，所以弹出3，然后2入栈。栈[2]。 - 处理
5：当前元素5大于栈顶元素2，直接入栈。栈[2, 5]。 - 处理
1：当前元素1小于栈顶元素5，所以弹出5；当前元素1继续小于栈顶元素2，所以弹出2，然后1入栈。栈[1]。
最终栈的内容是 [1]，这是一个单调递增栈。
总结：
单调栈通过维持栈内元素的单调性（递增或递减），能够帮助我们在许多算法问题中高效地找到所需的最小或最大值，减少不必要的元素，优化问题的求解。
💬 评论