stack

[caibirdme]

stack problems are sometimes a little bit difficult

[caibirdme]

Largest Rectangle in Histogram 这道题是一系列类似题目的基础,也是栈的一个常见应用场景--单调队列. 一个矩形的高其实就是连续区间里最小的那个值, 换句话说, 如果我们以某个值作为矩形的高, 那么这个矩形的长就是 高到左边第一个比它小的值以及高到右边第一个比它小的. 而这, 刚好就是我们维护一个单调队列的过程. 比如如下数组

x x 1 x x x 5 x x x x x 7 x x x x x 9

如果我们维护一个单调递增的队列, 当队列中是1 5 7 9时, 其实就意味这1到5之间的数都是大于等于5的,5到7之间都是大于等于7的, 7到9之间同理. 你可以发现, 这不就是这道题让我们找的吗, 以7为高的矩形面积就是(pos(9)-pos(5)+1)7, 以5为高的矩形面积就是(pos(9)-pos(1)+1)5 因此我们可以利用单调队列存储每个元素的下标, 当新元素小于栈顶, 就形成了形如 5 x x 7 x x 9 6这样的序列, 此时我们在弹出9之前可以把9进行计算, 以它为高的矩形面积就是(pos(6)-pos(7)+1)9, 继续弹出7, 然后计算以7为高的矩形面积, (pos(6)-pos(5)+1)7

这个算法非常重要, 后面有很多题目都直接依赖这种解法, 大多数都是把对应的问题压缩转化成一维序列, 使用这种办法解决.

[caibirdme]

Maximal Rectangle

这道题直接就是上一题的加强版, 在二维平面上找矩形最大面积. 我们通过枚举行, 以次行为底, 能够把这一行和之前行的数据压缩成一个一维数组, 直接利用之前的单调队列解法, 在O(n)的时间内计算出来结果, 整体复杂度就是O(n*m)

[caibirdme]

Verify Preorder Sequence in Binary Search Tree 对于一颗bst,先序遍历时, 是从根一直往左到第一个叶节点. 整个路径一直在减小. 当到达叶节点后, 下一个节点就是某个节点的右子树. 而且, 由于它是某个节点的右子树, 它一定大于它的父节点但小于爷爷节点. 举个例子, 8 6 3 2 [5], 对于5来说, 它肯定是右子树, 所以大于父节点,但是要小于爷爷节点, 因此它是3的右子树. 因此我们可以用栈, 一直pop,直到6, 得到8 6 5. 这时如果5有子树, 那么它的子节点都要大于3.

所以可以这样: 利用栈, 每次枚举一个数, 如果比lower_bound小就不合法. 如果比栈顶小,说明是某个数左子树, push进栈. 如果大于栈顶, 就说明是某个数的右子树, 一直pop, 然后更新lower_bound

        let mut lower_bound = std::i32::MIN;
        for v in preorder{
            if v < lower_bound {
                return false;
            }
            while let Some(&top) = q.last() {
                if v > top {
                    q.pop();
                    lower_bound = top;
                } else {
                    break;
                }
            }
            q.push(v);
        }

[caibirdme]

必须要熟悉并且能够快速实现树的三种遍历的非递归方法!!!

[caibirdme]

Closest Binary Search Tree Value II 这道题最直接的思路就是先找到距离target最接近的元素, 然后想办法找出最接近的k个元素. 实际上经过拆分发现这是3道题的结合, 因为follow up要求小于O(n), 所以是hard!! 很多题解都不满足这要求 T1: 找到bst中最接近target的数 T2: 给定一个有序数组, 找到数组中最接近target的k个数 T3: 非递归地输出bst的中序遍历

为什么有T3呢? 因为要求小于O(n), 因此我们不能通过中序遍历生成有序数组后再进行T2的操作, 需要边中序遍历边计算最接近的k个数.因此关键是T2怎么做.

由于k是固定的,因此我们可以考虑滑动窗口, 假如已经有k个有序的数 x .... , 这时新来一个y, 如果窗口向右滑动一位, x ... 后面的k-1个数都没变, 只是把x替换成y. 因此看窗口能不能滑动, 其实就是看 target离x近还是离y更近. 当发现target离x更近时, 由于数组有序, 之后的数肯定都比y大, 离target更远, 因此这时就可以直接退出了

[caibirdme]

Remove Duplicate Letters 这道题要求去除重复字母,并且输出字典序最小的. 字典序最小是关键. 通常对于这类问题都是先假设已经有了一个序列里存着答案了, 然后再来一个新元素, 思考怎么处理新元素. 假如新来了一个元素, 这个元素假如是c, 而我们已有的答案序列最后一个元素是e. 由于要找字典序最小的, 因此c可以放到e前面(当且仅当c后面还有e).

也就是说, 我们可以顺序枚举元素, 利用一个栈存储一个结果序列. 如果新元素比栈顶元素小, 且栈顶元素后面还有, 那么就可以把栈顶元素弹出.

[caibirdme]

Remove K Digits 这道题其实和Remove Duplicate Letters是一模一样的做法. 这种题目可以归结为, 从数组中删除一些元素, 使得剩下的满足xx最大or最小. 为什么这类题比较适合用栈来做呢? 因为栈天然就可以用来保存"顺序":

• 栈中元素底部的一定比顶部的先入栈
• 如果栈中元素再保持有序, 对于新元素很容易能够决定它可以被放到哪个位置

基于这种模型还可能出很多很多题目,但是大多数都换汤不换药, 因此要学会看清这种题目的本质