什么是单调栈？
单调递增栈,从栈底到栈顶依次递增（单调非递减栈:允许有相等）
单调递减栈,从栈底到栈顶依次递减（单调非递增栈:允许有相等）
单调栈的作用：
可以以 O(1) 的时间复杂度得知某个位置左右两侧比他大（或小）的数的位置，当你需要高效率获取某个位置左右两侧比他大（或小）的数的位置的的时候就可以用到单调栈。
- 求解数组中元素右边第一个比它小的元素的下标，从前往后，构造单调递增栈；
- 求解数组中元素右边第一个比它大的元素的下标，从前往后，构造单调递减栈；
- 求解数组中元素左边第一个比它小的元素的下标，从后往前，构造单调递减栈；
- 求解数组中元素左边第一个比它小的元素的下标，从后往前，构造单调递增栈。
范式：
单调递增栈
for(int i = 0; i < T.size(); i++){
while(! stk.empty() && stk.top() > T[i]){
stk.pop();
}
stk.push(A[i]);
}
单调递减栈
for(int i = T.size() - 1; i >= 0; i--){
while(! stk.empty() && T[i] >= stk.top()){
stk.pop();
}
stk.push(i);
}
网友评论