维持递增或递减

方法

栈内保持单调增(减), 当遇到不满足的数时, 把所有大于(小于)nums[i]的栈元素抛出. 对每个抛出的元素, 可能要结合它所在的位置作计算(栈内存的是index), 看是否是全局最优解.

用途

1. 要维持结果尽量递增(减), 如Remove Duplicate Letters.

2. 对某数nums[i], 找右边(左边)第一个比它大(小)的数. 比如next greater是典型的应用. Longest histogram, 对于块i, 找右边第一个比当前块小的块, 把两块之间的距离作为宽.

3. 对nums[i], 找右边(左边)比该数小的最大的数, 且对所有nums, 只保留最大的num即可. (132 Pattern).