day47 代码随想录算法训练营 单调栈专题2
1 今日打卡
柱状图中最大的矩形 84. 柱状图中最大的矩形 - 力扣（LeetCode）
2 接雨水
2.1 暴力法思路
暴力解法的本质是逐个位置计算接水量，步骤如下：
遍历数组中每一个位置（首尾位置无法接水，直接跳过）；
对每个位置 i：
找 i 左边（包括 i）的最大高度 maxLeft；
找 i 右边（包括 i）的最大高度 maxRight；
计算该位置的接水量：min(maxLeft, maxRight) - height[i]（结果≥0 才有效）；
累加所有位置的接水量，得到总水量。
2.2 暴力法实现代码
class Solution { public int trap(int[] height) { // 1. 获取数组长度 int len = height.length; // 2. 总接水量，初始化为0 int sum = 0; // 3. 遍历每个位置（逐个计算接水量） for (int i = 0; i < len; i++) { // 4. 首尾位置无法接水，直接跳过 if (i == 0 || i == len - 1) { continue; } // 5. 初始化：当前位置的左最大高度 = 当前高度（从当前位置往左找） int maxLeft = height[i]; // 6. 初始化：当前位置的右最大高度 = 当前高度（从当前位置往右找） int maxRight = height[i]; // 7. 找i左边（包括i）的最大高度 for (int j = i; j >= 0; j--) { if (height[j] > maxLeft) { maxLeft = height[j]; } } // 8. 找i右边（包括i）的最大高度 for (int j = i; j < len; j++) { if (height[j] > maxRight) { maxRight = height[j]; } } // 9. 计算当前位置的接水量：左右最大高度的较小值 - 当前高度 // （因为min(maxLeft, maxRight) ≥ height[i]，所以结果≥0） sum += Math.min(maxLeft, maxRight) - height[i]; } // 10. 返回总接水量 return sum; } }2.3 双指针优化思路
暴力解法的最大问题是：每个位置都要重复遍历左右找最大高度（比如位置 i 找左最大遍历 i 次，位置 i+1 又要遍历 i+1 次，大量重复计算）。
优化的核心是：
预处理两个数组：
maxLeft[i]：表示位置 i 及左边的最大高度（提前一次遍历算完）；
maxRight[i]：表示位置 i 及右边的最大高度（提前一次遍历算完）；
后续计算每个位置的接水量时，直接从预处理数组取值，无需重复遍历；
最终总接水量 = 累加每个位置 min(maxLeft[i], maxRight[i]) - height[i]（结果 > 0 才累加）。
2.4 双指针优化实现代码
class Solution { public int trap(int[] height) { // 1. 获取数组长度 int len = height.length; // 2. 边界处理：长度≤2时，无法形成“凹槽”接水，直接返回0 if (len <= 2) return 0; // 3. 总接水量，初始化为0 int sum = 0; // 4. 预处理数组1：maxLeft[i] = 位置i及左边的最大高度 int[] maxLeft = new int[len]; maxLeft[0] = height[0]; // 第一个位置的左最大高度就是自己 // 从左到右遍历，递推计算每个位置的左最大高度 for (int i = 1; i < len; i++) { // 递推公式：当前位置的左最大 = max(当前高度, 前一个位置的左最大) maxLeft[i] = Math.max(height[i], maxLeft[i - 1]); } // 5. 预处理数组2：maxRight[i] = 位置i及右边的最大高度 int[] maxRight = new int[len]; maxRight[len - 1] = height[len - 1]; // 最后一个位置的右最大高度就是自己 // 从右到左遍历，递推计算每个位置的右最大高度 for (int i = len - 2; i >= 0; i--) { // 递推公式：当前位置的右最大 = max(当前高度, 后一个位置的右最大) maxRight[i] = Math.max(height[i], maxRight[i + 1]); } // 6. 计算每个位置的接水量并累加 for (int i = 0; i < len; i++) { // 单个位置接水量 = 左右最大高度的较小值 - 当前高度 int count = Math.min(maxLeft[i], maxRight[i]) - height[i]; // 只有接水量>0时才累加（避免负数） if (count > 0) sum += count; } // 7. 返回总接水量 return sum; } }2.5 单调栈思路
一、单调栈解法的核心逻辑
1. 栈的定义
栈中存储的是 height 数组的索引，且索引对应的高度满足单调递减（这是关键）。
遇到比栈顶索引高度小的元素：压栈（继续找凹槽的右边界）；
遇到比栈顶索引高度大的元素：说明找到了凹槽的右边界，开始计算接水量。
2. 接水量的计算逻辑（核心公式）
当找到凹槽的右边界时，栈内元素的结构是：[左边界索引, 凹槽底部索引]，此时：
凹槽底部高度：height[mid]（mid 是栈顶弹出的索引）；
凹槽左边界高度：height[left]（left 是弹出 mid 后的新栈顶）；
凹槽右边界高度：height[right]（right 是当前遍历的索引）；
接水的高度：min(height[left], height[right]) - height[mid]；
接水的宽度：right - left - 1；
该凹槽的接水量：高度 × 宽度。
3. 整体流程
遍历数组的每个索引作为右边界；
若当前高度 > 栈顶索引的高度：循环弹出栈顶（凹槽底部），计算该凹槽的接水量；
若当前高度 ≤ 栈顶索引的高度：压栈；
累加所有凹槽的接水量，得到总水量。
单调栈接水量是按行来计算的，而双指针是按列来计算的。
2.6 单调栈实现代码
import java.util.Deque; import java.util.LinkedList; class Solution { public int trap(int[] height) { int len = height.length; if (len <= 2) return 0; // 边界：长度≤2无法接水 int sum = 0; // 总接水量 // 单调递减栈：存储height的索引，索引对应高度单调递减 Deque<Integer> stack = new LinkedList<>(); stack.push(0); // 先压入第一个索引作为初始值 // 遍历每个索引作为右边界 for (int right = 1; right < len; right++) { // 情况1：当前高度 ≤ 栈顶索引高度 → 保持单调递减，压栈 if (height[right] <= height[stack.peek()]) { stack.push(right); } // 情况2：当前高度 > 栈顶索引高度 → 找到凹槽右边界，计算接水量 else { // 循环处理：只要栈不空，且当前高度仍大于栈顶索引高度 while (!stack.isEmpty() && height[right] > height[stack.peek()]) { // 1. 弹出栈顶，作为凹槽底部索引 int mid = stack.pop(); // 弹出后栈空 → 无左边界，无法形成凹槽，退出循环 if (stack.isEmpty()) { break; } // 2. 弹出mid后的新栈顶，就是凹槽左边界索引 int left = stack.peek(); // 3. 计算接水高度：左右边界的较小值 - 凹槽底部高度 int h = Math.min(height[left], height[right]) - height[mid]; // 4. 计算接水宽度：右边界 - 左边界 - 1（中间的列数） int w = right - left - 1; // 5. 累加该凹槽的接水量 sum += h * w; } // 处理完当前凹槽后，将右边界压栈（作为新的左边界候选） stack.push(right); } } return sum; } }3 柱状图中最大的矩形
3.1 暴力法思路
暴力解法的本质是逐个柱子计算以其为高度的最大矩形面积，步骤如下：
遍历每一根柱子（索引i）；
对每个柱子i：
向左找第一个高度 < heights[i] 的柱子，记为左边界left；
向右找第一个高度 < heights[i] 的柱子，记为右边界right；
计算以heights[i]为高度的矩形面积：heights[i] × (right - left - 1)；
遍历过程中记录最大面积，最终返回。
3.2 暴力法实现代码
class Solution { public: int largestRectangleArea(vector<int>& heights) { // 1. 存储最大矩形面积，初始化为0 int sum = 0; // 2. 遍历每一根柱子，逐个计算以其为高度的最大矩形面积 for (int i = 0; i < heights.size(); i++) { // 3. 初始化左边界为当前柱子索引（向左找更小的柱子） int left = i; // 4. 初始化右边界为当前柱子索引（向右找更小的柱子） int right = i; // 5. 向左找第一个高度 < heights[i] 的柱子（左边界） for (; left >= 0; left--) { if (heights[left] < heights[i]) break; } // 6. 向右找第一个高度 < heights[i] 的柱子（右边界） for (; right < heights.size(); right++) { if (heights[right] < heights[i]) break; } // 7. 计算矩形宽度：右边界 - 左边界 - 1 int w = right - left - 1; // 8. 矩形高度：当前柱子的高度 int h = heights[i]; // 9. 更新最大面积：取当前最大和新计算面积的较大值 sum = max(sum, w * h); } // 10. 返回最大矩形面积 return sum; } };3.3 双指针思路
这道题的核心是：以每个柱子的高度为矩形高度，找到其左右第一个更矮的柱子作为边界，计算该高度下的最大宽度，最终取所有面积的最大值。双指针预处理优化的核心是通过两个数组提前计算每个柱子的左右边界，避免暴力法的重复遍历，将时间复杂度从 O (n²) 降到 O (n)，解决超时问题。
关键概念
左边界 leftMin[i]：第 i 根柱子左侧第一个高度 < heights[i] 的柱子索引（无则设为 -1，虚拟左边界）；
右边界 rightMin[i]：第 i 根柱子右侧第一个高度 < heights[i] 的柱子索引（无则设为 n，虚拟右边界）；
矩形宽度：rightMin[i] - leftMin[i] - 1（虚拟边界保证所有柱子的宽度计算公式统一）；
矩形面积：heights[i] × 宽度（以当前柱子高度为矩形高度的最大面积）。
预处理逻辑（核心优化）
计算 leftMin：从左到右遍历，利用已计算的左边界 “跳着找”（若前一个柱子高度 ≥ 当前柱子，直接跳到前一个柱子的左边界，避免重复比较）；
计算 rightMin：从右到左遍历，逻辑与 leftMin 对称；
最终计算：遍历所有柱子，用预处理的边界计算面积，取最大值。
3.4 双指针实现代码
class Solution { public int largestRectangleArea(int[] heights) { int n = heights.length; // 边界处理：空数组返回0，单柱子返回自身高度 if (n == 0) return 0; if (n == 1) return heights[0]; // 1. 预处理左边界数组：leftMin[i] = 左侧第一个更矮柱子的索引（无则为-1） int[] leftMin = new int[n]; leftMin[0] = -1; // 最左柱子无左侧柱子，设为虚拟左边界-1 for (int i = 1; i < n; i++) { int t = i - 1; // 先假设左边界是前一个柱子 // 核心优化：跳着找——若t位置柱子≥当前高度，直接跳到t的左边界 while (t >= 0 && heights[t] >= heights[i]) { t = leftMin[t]; } leftMin[i] = t; // 最终t就是i的左边界 } // 2. 预处理右边界数组：rightMin[i] = 右侧第一个更矮柱子的索引（无则为n） int[] rightMin = new int[n]; rightMin[n - 1] = n; // 最右柱子无右侧柱子，设为虚拟右边界n for (int i = n - 2; i >= 0; i--) { int t = i + 1; // 先假设右边界是后一个柱子 // 核心优化：跳着找——若t位置柱子≥当前高度，直接跳到t的右边界 while (t < n && heights[t] >= heights[i]) { t = rightMin[t]; } rightMin[i] = t; // 最终t就是i的右边界 } // 3. 遍历所有柱子，计算最大面积 int maxArea = 0; for (int i = 0; i < n; i++) { // 宽度：右边界 - 左边界 - 1（虚拟边界保证公式统一） int width = rightMin[i] - leftMin[i] - 1; // 面积：高度 × 宽度 int area = heights[i] * width; // 更新最大面积 maxArea = Math.max(maxArea, area); } return maxArea; } // 测试用例：直接运行验证 public static void main(String[] args) { Solution solution = new Solution(); int[] heights = {2, 1, 5, 6, 2, 3}; System.out.println(solution.largestRectangleArea(heights)); // 输出10（符合预期） } }3.5 单调栈思路
核心目标：以每个柱子的高度为矩形高度，找到它「左右第一个更矮的柱子」作为边界，计算该高度下的最大面积，最终取所有面积的最大值。
单调栈的作用：用「单调递增栈」（栈内索引对应高度从小到大）实时找每个柱子的左右边界，弹出栈顶时就能拿到完整的边界信息。
哨兵的作用：
头部哨兵（高度 0）：确保栈永远不会空，避免peek()返回 null 触发空指针；
末尾哨兵（高度 0）：强制弹出栈内所有剩余元素，确保每个柱子都能计算面积。
为什么首尾加哨兵？
头部哨兵（0）：确保栈永远有元素，st.peek() 不会返回 null，避免空指针；
末尾哨兵（0）：强制弹出栈内所有剩余元素（比如最后几个柱子），确保每个柱子都计算面积。
为什么用 while 循环？
因为当前高度可能比多个栈顶元素小（比如 i=5 时，2 比 6、5 都小），需要循环弹出所有比当前高度大的栈顶，逐个计算面积。
宽度公式 right - left - 1 怎么来的？
left 是 mid 左侧第一个更矮的柱子，right 是 mid 右侧第一个更矮的柱子；
中间能支撑 mid 高度的列数 = 右边界索引 - 左边界索引 - 1（比如 left=2，right=5 → 列数 = 5-2-1=2，对应索引 3、4）。
五、总结（3 句话记住核心）
栈的作用：单调递增栈存储索引，弹出时能拿到「当前柱子的左右第一个更矮边界」；
哨兵的作用：首尾加 0，避免栈空和遗漏末尾柱子；
面积计算：弹出栈顶时，用「右边界 - 左边界 - 1」算宽度，栈顶高度算高度，相乘就是该柱子的最大面积。
3.6 单调栈实现代码
class Solution { public int largestRectangleArea(int[] heights) { // 1. 边界处理：如果只有1根柱子，面积就是它自己的高度 int len = heights.length; if (len == 1) return heights[0]; // 2. 构造「首尾加哨兵」的新数组（核心！避免边界问题） // 新数组长度 = 原数组长度 + 2（头部1个哨兵，尾部1个哨兵） int[] newHeights = new int[len + 2]; // 把原数组的值拷贝到新数组的「中间位置」（索引1 ~ len） for (int i = 0; i < len; i++) { newHeights[i + 1] = heights[i]; } // 头部哨兵（索引0）：高度0（比所有真实柱子都矮） newHeights[0] = 0; // 末尾哨兵（索引len+1）：高度0（比所有真实柱子都矮） newHeights[len + 1] = 0; // 3. 初始化单调递增栈：存储「新数组的索引」，栈内索引对应高度递增 // 用LinkedList实现Deque，是Java推荐的栈写法（比Stack类更高效） Deque<Integer> st = new LinkedList<>(); st.push(0); // 先压入头部哨兵的索引，确保栈永远不会空 // 4. 存储最大矩形面积，初始为0 int res = 0; // 5. 遍历新数组的所有元素（包括首尾哨兵） for (int i = 0; i < newHeights.length; i++) { // 核心逻辑：当前高度 < 栈顶索引的高度 → 找到栈顶的右边界，开始计算面积 // while循环：确保弹出所有比当前高度大的栈顶元素 while (newHeights[i] < newHeights[st.peek()]) { // 步骤1：弹出栈顶索引 → 这是要计算面积的「柱子mid」 int mid = st.pop(); // 步骤2：确定边界 int right = i; // 右边界 = 当前遍历的索引（第一个比mid矮的柱子） int left = st.peek(); // 左边界 = 弹出mid后新的栈顶（第一个比mid矮的柱子） // 步骤3：计算矩形宽度 = 右边界 - 左边界 - 1（中间的列数） int w = right - left - 1; // 步骤4：矩形高度 = 柱子mid的高度（这是该宽度下能支撑的最大高度） int h = newHeights[mid]; // 步骤5：更新最大面积（取当前最大值和新计算面积的较大值） res = Math.max(res, h * w); } // 当前高度 ≥ 栈顶索引的高度 → 栈保持递增，压入当前索引 st.push(i); } // 6. 返回最大面积 return res; }
