单调栈的应用

单调栈是一种特殊的栈,其中的元素都保持单调递增或单调递减的顺序。根据顺序的不同,可以分为单调递增栈和单调递减栈。

左边第一个

从左到右遍历数组，当我们遇到一个新元素时，将它与栈顶元素比较：

单增栈，如果新元素大于或等于栈顶元素，直接将新元素入栈；如果新元素小于栈顶元素，就不断地弹出栈顶元素，直到栈顶元素小于等于新元素，或者栈为空；在弹栈过程中，对于每个被弹出的元素，新元素就是它右边第一个比它小的元素；弹出操作结束后，如果栈不为空，当前栈顶元素就是新元素左边第一个比它小的元素；最后新元素入栈。
单减栈，如果新元素小于或等于栈顶元素，直接将新元素入栈；如果新元素大于栈顶元素，就不断地弹出栈顶元素，直到栈顶元素大于等于新元素，或者栈为空；在弹栈过程中，对于每个被弹出的元素，新元素就是它右边第一个比它大的元素；弹出操作结束后，如果栈不为空，当前栈顶元素就是新元素左边第一个比它大的元素；最后新元素入栈。