单调栈
情形一:寻找一个数左边第一个小于它的数
情形二:寻找一个数左边第一个小于它的数的下标
情形三:寻找一个数右边第一个大于它的数
情形四:寻找一个数右边第一个大于它的数的下标
https://algo.itcharge.cn/03.Stack/02.Monotone-Stack/01.Monotone-Stack/
单调队列
情形:力扣P239——滑动窗口最大值和最小值
P739每日温度
P84柱状图
P42接雨水
先考虑暴力怎么做,然后考虑每个窗口内是否有用不到的值,用栈或队列进行当前值和队尾值的判断,使结构内满足单调性即可
核心思路:
先考虑题目应该是以上四个情形的一个或多个情形,考虑遍历过程中,当前元素如果比栈顶元素小,入不入栈;比栈顶元素大,入不入栈,然后套模版即可
算面积的题,可能使用从左到右,从右到左两次单调栈,记录到两个数组
模版之一:
// 寻找一个数左边第一个小于它的数
Deque<Integer> stack = new LinkedList<>();
for(int i=0; i<n; i++){
while(!stack.isEmpty() && nums[i] <= stack.peek()){
stack.pop();
// 出栈,比x大的元素均可出栈
}
if(!stack.isEmpty()){
xxxx
// 做一些操作,打印或者计算或者记录到数组
}
stack.push(nums[i]);
}