单调栈(算法)

单调栈的定义与类型单调栈是一种栈结构内部元素保持严格的单调递增或单调递减顺序。分为两种基本类型单调递增栈栈底到栈顶元素逐渐增大单调递减栈栈底到栈顶元素逐渐减小核心原理与典型应用在遍历数组时利用栈来记录尚未找到“下一个更大/更小”元素的下标。当遇到一个破坏单调性的元素时就依次弹出栈内元素并当场结算这些弹出元素的答案。主要解决两类问题寻找数组中每个元素左边/右边第一个比它大/小的元素。计算特定几何结构的极值如凹槽面积、矩形面积基础代码模板右侧第一个更大元素public int[] nextGreaterElement(int[] nums) { int n nums.length; int[] res new int[n]; DequeInteger stack new ArrayDeque(); for (int i 0; i n; i) { while (!stack.isEmpty() nums[i] nums[stack.peek()]) { int idx stack.pop(); res[idx] nums[i]; } stack.push(i); } while (!stack.isEmpty()) { res[stack.pop()] -1; } return res; }右侧第一个更小元素仅需修改比较符号while (!stack.isEmpty() nums[i] nums[stack.peek()]) { // 处理逻辑 }经典问题解析接雨水问题(LeetCode 42)思路按列求雨水。使用单调递减栈栈底最大当height[i] height[stack.peek()]时形成凹槽弹出bottom作为底部。若栈空则无法蓄水否则left stack.peek()为左边界。宽度 i - left - 1。高度 min(height[left], height[i]) - height[bottom]。public int trap(int[] height) { DequeInteger stack new ArrayDeque(); int res 0; for (int i 0; i height.length; i) { while (!stack.isEmpty() height[i] height[stack.peek()]) { int bottom stack.pop(); if (stack.isEmpty()) break; int left stack.peek(); int w i - left - 1; int h Math.min(height[left], height[i]) - height[bottom]; res w * h; } stack.push(i); } return res; }最大矩形问题(LeetCode 84)思路寻找每个柱子左右两边第一个比它矮的柱子宽度 right - left - 1高度 heights[i]。使用单调递增栈栈底最小当heights[i] heights[stack.peek()]时触发public int largestRectangleArea(int[] heights) { int n heights.length; int[] newHeights new int[n 2]; // 哨兵技巧避免越界 System.arraycopy(heights, 0, newHeights, 1, n); DequeInteger stack new ArrayDeque(); int res 0; for (int i 0; i newHeights.length; i) { while (!stack.isEmpty() newHeights[i] newHeights[stack.peek()]) { int h newHeights[stack.pop()]; int left stack.peek(); int w i - left - 1; res Math.max(res, h * w); } stack.push(i); } return res; }时间复杂度与空间复杂度时间复杂度O(n)每个元素仅入栈出栈一次空间复杂度O(n)栈的存储开销关键注意事项下标存储优于值存储便于计算宽度比较条件选择严格单调/非严格单调需根据题意调整推荐使用ArrayDeque代替传统Stack类