问题描述 链接到标题
简述 链接到标题
单调栈(monotone stack)是指栈内元素(栈顶到栈底)都是(严格)单调递增或者递减的栈。
单调递增栈(从栈顶到栈底)：只有比栈顶小的才能入栈，否把栈顶元素弹出，直到栈为空或者或者待处理的元素小于栈顶元素，将元素入栈，适用于求解第一个大于某元素的数的情况；
单调递减栈，与递增栈相反，适用于求解第一个小于某位置元素的数；
判断方法 链接到标题
单调递增/递减栈一般根据出栈后顺序来决定，例如栈内顺序[1, 2, 6]，出栈后顺序[6, 2, 1]，这就是单调递减栈。
哨兵技巧 链接到标题
对于有些时候，如果会用到数组的全部元素，即栈中的元素最后都要出栈，那么很可能因为没有考虑边界而无法通过。所以我们可以使用哨兵法。
例如在{1, 3, 4, 5, 2, 9, 6}末尾添加一个-1作为哨兵，变成了 {1, 3, 4, 5, 2, 9, 6, -1}，这种技巧可以简化代码逻辑。