Algorithm - Monotonic Stack
Created by : Mr Dk.
2020 / 12 / 02 22:46
Nanjing, Jiangsu, China
About
最近刷 LeetCode 经常会碰到 单调栈，特此总结一下。顾名思义，单调栈就是栈内序列是单调递增或单调递减的栈。单调递增栈有什么用途？有哪些使用场景？
Next Higher Man
试想一些身高不同的人无序站队，现在想要知道每一个人一回头能看见的第一个人有多高，也就是身后第一个比他高的人的身高。暴力解法需要 O(N^2) 的复杂度。
如果从后向前遍历，用一个单调栈就可以记录已经每一个遍历位置之前比它高的人的身高。具体地，如果栈为空，或当前元素比栈顶元素小，那么就将当前元素入栈；如果当前元素比栈顶大，那么不停出栈，直到栈为空或当前元素比栈顶元素小为止，然后将当前元素入栈。
这个逻辑的本质是，栈中存放了当前位置之后 身高高于当前位置 的所有身高。如果当前位置的身高低于栈顶位置的身高，那么当前身高可能会作为之前位置中更矮的人后头看到的第一个高于自己的身高，所以要入栈；而如果当前位置的身高高于栈顶身高，那么当前身高将会遮掉栈中之后位置所有低于自己的身高，所以需要不断 pop 栈中元素，直到栈为空 (没有元素比自己高了) 或当前身高低于栈顶身高 (无法遮住后面更高的人)。
|
| |
| | | |
| | | | |
| | | | |
0 1 2 3 4
从 4 位置开始。4 回头看发现栈空且没有比自己更高的人了，于是入栈：
4 |
3 位置回头看，发现自己遮不住 4 (低于栈顶元素)，于是入栈：
3 4 |
2 位置回头看，发现自己比 3 高，对于更前面的位置，完全可以遮住 3，于是将 3 弹出；但是自己仍然遮不住 4，于是入栈：
2 4 |
1 位置回头看，发现自己能盖住 2 但盖不住 4，对于之前位置的元素来说，其实已经不可能看到 2 了，于是将其出栈，自身入栈：
1 4 |
0 位置回头看，发现自己盖不过 1 也盖不住 4，于是自身入栈：
0 1 4 |
可以看到，该栈形成了一个从栈顶开始递增的序列。在时间复杂度上，每个元素实际上只会出入栈一次，所以是 O(n)。
Biggest Number
这是今天刷一道 hard 的 LeetCode 题目时用到的一个子功能，挺有意思。给定一个无序的数组，需要找出一个指定长度的子序列，使得这个子序列组成的数的数值最大。比如，对于 [ 3, 5, 2, 8, 6, 4 ]，从其中组成的最大的三位数应该是 864，这里实际上也用到了单调栈的思想。
既然要组成最大的三位数，那么我们肯定希望位数越高 (越左边) 的数尽可能大，依次单调递减。这里需要特别注意的情况有以下几个：
- 由于位数是固定的 (比如三位数)，因此单调栈的容量也是固定的
- 贪心可能会有问题，栈中的内容并不严格递减，考虑
[ 3, 5, 2, 8, 9, 4 ]的情况：如果按照单调栈的思想，最终栈中将只会剩下9和4，从而无法满足三位数的要求 - 也就是说在 pop 元素时还需要考虑剩余序列的长度
最终实现的代码如下，仍有优化空间：
- 条件分支上的优化 (先后顺序，技巧等)
- 通过参数支持动态传入比较函数 (类似 STL 的
sort())
vector<int> decending_stack(vector<int> &source, int capacity) {
// capacity <= source.size()
// 栈容量不可高于序列长度，否则永远不可能找到这样的序列
vector<int> stack;
stack.reserve(capacity);
if (capacity <= 0 || capacity > (int) source.size()) {
return stack;
}
for (size_t i = 0; i < source.size(); i++) {
if (stack.empty()) {
// 栈为空时，直接 push
stack.push_back(source[i]);
} else if (source[i] <= stack[stack.size() - 1]) {
// 当前元素不高于栈顶元素，那么可以作为栈顶元素的更低位
if (stack.size() < (size_t) capacity) {
stack.push_back(source[i]);
}
} else {
// 栈不为空，当前元素高于栈顶元素
// 此时需要 pop 直至栈空，或当前元素不高于栈顶
// 重要的限制条件：考虑序列中的剩余元素，如果不够用，则不能 pop
while (!stack.empty() &&
source[i] > stack[stack.size() - 1] &&
stack.size() + source.size() - i > (size_t) capacity) {
// stack element + (remaining element) > stack capacity
stack.pop_back();
}
// 当前元素入栈
stack.push_back(source[i]);
}
}
return stack;
}