【代码随想录Day47】单调栈Part02

42. 接雨水

题目链接/文章讲解：代码随想录
视频讲解：单调栈，经典来袭！LeetCode:42.接雨水_哔哩哔哩_bilibili

思路概述

1. 问题理解：我们需要计算在给定柱子高度之间可以接住的雨水总量。雨水的量取决于柱子的高度和它们之间的相对位置。

2. 使用栈的数据结构：我们使用栈来存储柱子的索引，以便在遍历时能够快速找到可能的边界柱子。

3. 遍历柱子：遍历所有柱子。在每一步：

   • 如果当前柱子的高度大于栈顶柱子的高度，意味着我们可以开始计算雨水量。
   • 弹出栈顶索引，得到当前柱子的索引，称为“中间柱子”。

4. 计算雨水量：

   • 检查栈是否为空。如果栈为空，说明没有左边界，无法计算雨水量。
   • 使用栈顶的索引作为左边界，当前柱子的索引作为右边界，计算可以接住的水的高度。
   • 计算水的宽度，即左右边界之间的距离。

5. 更新总雨水量：将计算得到的雨水量累加到总量中。

6. 压入当前柱子索引：将当前柱子的索引压入栈中，以便在后续的计算中作为新的边界。

7. 返回结果：遍历结束后，返回累加的雨水总量。

总结

这种方法利用栈的特性有效地计算了雨水接收量。通过在遍历过程中动态更新栈，能够快速找到左右边界，从而高效地进行雨水量的计算。整体时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是柱子的数量。

class Solution {public int trap(int[] height) {if (height == null || height.length == 0) {return 0; // 如果输入为空或长度为零，直接返回0}Stack<Integer> stack = new Stack<>();int len = height.length;int sum = 0;for (int i = 0; i < len; i++) {while (!stack.isEmpty() && height[i] > height[stack.peek()]) {int mid = stack.pop(); // 弹出当前的高度if (stack.isEmpty()) {break; // 如果栈空了，说明没有左侧边界，退出循环}// 计算当前可以接到的水的高度int h = Math.min(height[i], height[stack.peek()]) - height[mid];// 计算宽度int w = i - stack.peek() - 1; // 注意宽度应该是两边的边界之间的距离sum += h * w; // 计算并累加总水量}stack.push(i); // 将当前柱子的索引压入栈中}return sum; // 返回总的接水量}
}

84.柱状图中最大的矩形

题目链接/文章讲解：代码随想录
视频讲解：单调栈，又一次经典来袭！ LeetCode：84.柱状图中最大的矩形_哔哩哔哩_bilibili

思路概述

1. 问题理解：

• 给定一个柱子的高度数组（代表直方图中每个柱子的高度），我们需要找出其中可以形成的最大矩形的面积。
• 矩形的高度由柱子的高度决定，而宽度则由相邻的柱子决定。

2. 使用栈来处理柱子：

• 利用栈来存储柱子的索引，以便在遍历过程中能够快速找到较小的柱子，从而确定矩形的高度和宽度。
• 栈的特点是后进先出（LIFO），适合处理这种需要回溯的场景。

3. 遍历柱子：

• 通过一次遍历来处理每一个柱子。对于每一个柱子：
  • 如果当前柱子的高度大于栈顶柱子的高度，则可以将当前柱子的索引压入栈中。
  • 如果当前柱子的高度小于等于栈顶柱子的高度，则需要计算以栈顶柱子为最小高度的矩形面积。

4. 计算矩形面积：

• 当弹出栈顶柱子时，确定以该柱子为最小高度的矩形的高度和宽度：
  • 高度是弹出的柱子的高度。
  • 宽度是当前索引与栈顶索引之间的差值（如果栈为空，说明该柱子是最左边的柱子）。
• 计算面积并与当前的最大面积进行比较，更新最大面积。

5. 处理边界情况：

• 在遍历结束后，为了确保栈中所有柱子都能被处理，添加一个高度为0的伪柱。这样可以确保所有剩余的柱子都能计算出相应的面积。

6. 最终结果：

• 遍历完成后，返回记录的最大矩形面积。

总结：

这个算法的核心在于通过栈的使用来高效地管理柱子的索引，从而在一个线性时间复杂度内计算出最大矩形面积。相比于暴力法（O(n^2)），这种方法大大提高了效率，适合处理大规模数据。栈的使用使得我们能够在遇到较小柱子时及时计算出可能的矩形面积，同时保持对柱子索引的有效管理。

class Solution {public int largestRectangleArea(int[] heights) {Stack<Integer> stack = new Stack<>();  // 创建一个栈来存储柱子的索引int max = 0;  // 初始化最大矩形面积为0int len = heights.length;  // 获取柱子数组的长度// 遍历每个柱子，最后一个循环是为了处理栈中的剩余柱子for (int i = 0; i <= len; i++) {// 处理边界情况，添加一个高度为0的伪柱，以确保栈中所有柱子都能被处理int currentHeight = (i == len) ? 0 : heights[i];// 当当前柱子高度小于栈顶柱子的高度时，开始计算面积while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {int mid = stack.pop();  // 弹出栈顶元素，获取当前柱子的索引int h = heights[mid];  // 获取弹出柱子的高度// 计算矩形的宽度// 如果栈为空，说明mid是最左边的柱子，宽度等于当前索引i// 否则，宽度为当前索引i减去栈顶元素的索引再减去1int w = stack.isEmpty() ? i : i - stack.peek() - 1;// 更新最大矩形面积max = Math.max(max, h * w);}// 将当前柱子的索引入栈stack.push(i);}return max;  // 返回计算出的最大矩形面积}
}