数据结构——单调栈

单调栈 定义

单调递增栈：单调递增栈就是从栈底到栈顶数据是从小到大 单调递减栈：单调递减栈就是从栈底到栈顶数据是从大到小

实现

以单调递增栈为例，向栈中推入元素时，如果栈顶元素比当前元素大，则将栈顶元素推出，直到栈顶元素比当前元素小或者栈为空，然后将当前元素推入栈中。

stack sta;
for (遍历数组)
{
    while (栈不为空 && 栈顶元素大于当前元素)
        sta.pop();
    sta.push(当前元素);
}

作用

找到左边（右边）第一个比当前元素小（大）的元素。

例题

LeetCode 84