单调栈
单调栈实际上就是栈，只是限制要比普通的栈更严格而已了。要求是每次入栈的元素必须要有序（如果新元素入栈不符合要求，则将之前的元素出栈，直到符合要求再入栈），使之形成单调递增/单调递减的一个栈。
- 单调递增栈：只有比栈顶小的才能入栈，否则就把栈顶出栈后，再入栈。出栈时可能会有一些计算。适用于求解第一个大于该位置元素的数；
- 单调递减栈：与单调递增栈相反。适用于求解第一个小于该位置元素的数。
代码实现¶
template<
class T,
class Container = deque<T>,
class Compare = less<typename Container::value_type>
>
class monotonous_stack {
private:
stack<T, Container> _stack;
Compare _compare;
public:
monotonous_stack(): _compare() {}
explicit monotonous_stack(const Compare& __compare): _compare(__compare) {}
T& top() {
return _stack.top();
}
size_t size() {
return _stack.size();
}
bool empty() {
return _stack.size() == 0;
}
void push(
const T& value,
function<void()> before_satisfy_pop = [](){},
function<void()> on_satisfied = [](){}
) {
while (!_stack.empty() && _compare(value, _stack.top())) {
before_satisfy_pop();
_stack.pop();
}
on_satisfied();
_stack.push(value);
}
void pop() {
_stack.pop();
}
};
简单使用¶
// 默认参数
monotonous_stack<TYPE> mstack1;
// 默认使用 deque 作为容器
priority_queue<TYPE, deque<TYPE>> mstack2;
// 默认使用 less 比较函数，单调递减栈
priority_queue<TYPE, deque<TYPE>, less<TYPE>> mstack3;
print_mstack(mstack3); // 3 2 1
// greater 比较函数，单调递增栈
priority_queue<TYPE, deque<TYPE>, greater<TYPE>> mstack4;
print_mstack(mstack4); // 1 2 3
自定义比较函数¶
auto compare = [](pair<int, int>& a, pair<int, int>& b) { return a.first >= b.first; };
monotonous_stack<pair<int, int>, deque<pair<int, int>>, decltype(compare)> mstack1(compare);
monotonous_stack<pair<int, int>, deque<pair<int, int>>, auto(*)(pair<int, int>,pair<int, int>)->bool> mstack2([](pair<int, int> a, pair<int, int> b) {
return a.second >= b.second;
});