单调栈是一种特殊的栈,其中的元素都保持单调递增或单调递减的顺序。根据顺序的不同,可以分为单调递增栈和单调递减栈。
左边第一个
从左到右遍历数组，当我们遇到一个新元素时，将它与栈顶元素比较：
- 单增栈，如果新元素大于或等于栈顶元素，直接将新元素入栈；如果新元素小于栈顶元素，就不断地弹出栈顶元素，直到栈顶元素小于等于新元素，或者栈为空；在弹栈过程中，对于每个被弹出的元素，新元素就是它右边第一个比它小的元素；弹出操作结束后，如果栈不为空，当前栈顶元素就是新元素左边第一个比它小的元素；最后新元素入栈。
- 单减栈，如果新元素小于或等于栈顶元素，直接将新元素入栈；如果新元素大于栈顶元素，就不断地弹出栈顶元素，直到栈顶元素大于等于新元素，或者栈为空；在弹栈过程中，对于每个被弹出的元素，新元素就是它右边第一个比它大的元素；弹出操作结束后，如果栈不为空，当前栈顶元素就是新元素左边第一个比它大的元素；最后新元素入栈。
Monotonic Increasing Stack
许可协议
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。
分享文章
