什么时候会用到单调栈（递增递减栈）的思想

自己在学习栈的时候接触到了一种算法叫单调栈（递增递减栈）。最典型的问题就是largest rectangle in histogram。但是后来自己做题发现单调栈的应用非常多，思路也很巧妙，但是不知道这个思路解决问题的共性是什么。比如下面这两个问题，为什么我们会想到用单调栈呢？

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer.

Find the smallest integer after remove k digits.

单调栈何时用： 为任意一个元素找左边和右边第一个比自己大/小的位置，用单调栈
用递增单调栈还是递减单调栈：递减栈会剔除波谷，留下波峰；递增栈剔除波峰，留下波谷

这个贴不错, 我个人感觉是看题.

你提到了两个题, 分别是 316 Remove Duplicate Letters, 402 Remove K Digits

其实不止, 你会用到单调栈的还包括有 84 Largest Rectangle in Histogram | 85 (84变形), 42 Trapping Rain Water, 739. Daily Temperatures 321. Create Maximum Number.

在我看来, 这些题里面多多少少都用到了 155 min stack | max stack 这种形式, 只不过具体计算方法略有差别.

基本上对于每个点 [j], 题里的目的都是在找 j 左边 或者 右边 比 n[j] 大 | 小, 但是是 [inf]  或者 [sup] 的数字. 似乎并没有一个特别标准的答案说哪个题必须用那个, 但是找比当前数字大 | 小的时候, 确实无非是 inf 或者 sup..

单调栈题目汇总，欢迎补充！

求最值的时候，最后结果有单调性

肥宅快乐水 发表于 2018-7-4 05:11
这个贴不错, 我个人感觉是看题.

你提到了两个题, 分别是 316 Remove Duplicate Letters, 402 Remove K D ...

看出你的数学基础啦~点个赞吧~

idatascience 发表于 2018-7-4 09:14
看出你的数学基础啦~点个赞吧~

怎么样, 我这个b装的还可以把.

无形装b, 最为致命

肥宅快乐水 发表于 2018-7-4 09:45
怎么样, 我这个b装的还可以把.

无形装b, 最为致命

嗯，老母亲忍不住流下了喜悦的泪水

idatascience 发表于 2018-7-4 09:58
嗯，老母亲忍不住流下了喜悦的泪水

是你这个老母亲的样子么

可以说很形象了

idatascience 发表于 2018-7-4 09:58
嗯，老母亲忍不住流下了喜悦的泪水

老母亲您今年高寿啊..