单调栈用法

一、什么时候适合用单调栈题目要求为每个元素找左边/右边第一个比它大或小的元素且暴力 O(N²) 会超时 → 用单调栈。这是最核心的信号。看到第一个更大 / 第一个更小 / 下一个更大 / 下一个更小这类字眼基本就是单调栈。二、典型特征清单满足以下任意一条就该考虑单调栈特征说明① 找第一个更 X左边/右边第一个更大、更小、更高、更矮、更暖……② 求边界区间每个元素能向左/右扩展多远如最大矩形宽度③ 需要下一个更大/小元素Next Greater / Smaller Element 系列④ 数组 线性时间要求暴力 O(N²) 不行想要 O(N)⑤ 元素之间有遮挡关系后面的元素让前面的失效如接雨水、柱状图三、方向与单调性的对应表这是最实用的速查表决定你用递增栈还是递减栈、从左扫还是从右扫要找什么遍历方向栈的单调性左边第一个更小从左往右递增栈栈底小→栈顶大左边第一个更大从左往右递减栈右边第一个更小从右往左递增栈右边第一个更大从右往左递减栈记法找更小 → 递增栈找更大 → 递减栈找右边 → 从右往左扫每日温度是找右边第一个更大 → 从右往左扫、递减栈只不过它常用从左扫的写法效果一样。四、代码参考1、找左边第一个更小// 从左到有维护递增栈 // 如果左边没有更小的表示为-1 public int[] findLM(int[] nums) { int n nums.length; DequeInteger stack new ArrayDeque(); int[] ret new int[n]; for(int i 0; i n; i) { while(!stack.isEmpty() nums[stack.peek()] nums[i]) { stack.pop(); } ret[i] stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } return ret; }2、找左边第一个更大// 从左到右维护递减栈 // 如果左边没有更大的表示为-1 public int[] findLMax(int[] nums) { int n nums.length; DequeInteger stack new ArrayDeque(); int[] ret new int[n]; for(int i 0; i n; i) { while(!stack.isEmpty() nums[stack.peek()] nums[i]) { stack.pop(); } ret[i] stack.isEmpty() ? -1 : stack.peek(); stack.push(i); } return ret; }3、找右边第一个最小// 从右到左维护递增栈 // 如果左边没有更小的表示为n public int[] findRMin(int[] nums) { int n nums.length; DequeInteger stack new ArrayDeque(); int[] ret new int[n]; for(int i n-1; i 0; i--) { while(!stack.isEmpty() nums[stack.peek()] nums[i]) { stack.pop(); } ret[i] stack.isEmpty() ? n : stack.peek(); stack.push(i); } return ret; }4、找右边第一个最大// 从右到左维护递减栈 // 如果左边没有更大的表示为n public int[] findRMax(int[] nums) { int n nums.length; DequeInteger stack new ArrayDeque(); int[] ret new int[n]; for(int i n-1; i 0; i--) { while(!stack.isEmpty() nums[stack.peek()] nums[i]) { stack.pop(); } ret[i] stack.isEmpty() ? n : stack.peek(); stack.push(i); } return ret; }