当前位置：首页 > news >正文

【单调栈】|代码随想录算法训练营第42天|42. 接雨水、 84.柱状图中最大的矩形

news 2025/8/28 18:04:59

刷题神器

代码随想录

往期回顾

>【单调栈】|代码随想录算法训练营第41天|739. 每日温度、 496.下一个更大元素 I、503.下一个更大元素II

题目

42. 接雨水

题目：题目链接
文章：文章讲解
视频：视频讲解

学后思路

使用单调递增栈解决，注意计算面积找两边最高，右侧最高是当前遍历的值，左侧最高是栈内的第二个值

解法1:

class Solution {public int trap(int[] height){int size = height.length;if (size <= 2) return 0;// in the stack, we push the index of array// using height[] to access the real heightStack<Integer> stack = new Stack<Integer>();stack.push(0);int sum = 0;for (int index = 1; index < size; index++){int stackTop = stack.peek();if (height[index] < height[stackTop]){stack.push(index);}else if (height[index] == height[stackTop]){// 因为相等的相邻墙，左边一个是不可能存放雨水的，所以pop左边的index, push当前的indexstack.pop();stack.push(index);}else{//pop up all lower valueint heightAtIdx = height[index];while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){// 栈的第一个元素是中间值，弹出后的栈顶是左侧值int mid = stack.pop();if (!stack.isEmpty()){// 左侧值int left = stack.peek();//计算高度差int h = Math.min(height[left], height[index]) - height[mid];//计算宽度int w = index - left - 1;//计算面积int hold = h * w;if (hold > 0) sum += hold;stackTop = stack.peek();}}stack.push(index);}}return sum;}
}

题目总结
- 当遍历值等于栈顶值的时候，压栈和弹出再压栈对比，弹出再压栈少计算一次
- 注意获取左右最大高度的逻辑，当前遍历值大于栈顶值，为右侧第一个最大高度，栈中第二个值为左侧第一个最大高度

84.柱状图中最大的矩形

题目：题目链接
文章：文章讲解
视频：视频讲解

学后思路
单调递减栈，首尾加0，处理递增数组和递减数组

解法一:

class Solution {int largestRectangleArea(int[] heights) {Stack<Integer> st = new Stack<Integer>();// 数组扩容，在头和尾各加入一个元素 处理 456 或者 654 这种情况的数组int [] newHeights = new int[heights.length + 2];newHeights[0] = 0;newHeights[newHeights.length - 1] = 0;for (int index = 0; index < heights.length; index++){newHeights[index + 1] = heights[index];}heights = newHeights;st.push(0);int result = 0;// 第一个元素已经入栈，从下标1开始for (int i = 1; i < heights.length; i++) {// 注意heights[i] 是和heights[st.top()] 比较 ，st.top()是下标if (heights[i] > heights[st.peek()]) {st.push(i);} else if (heights[i] == heights[st.peek()]) {st.pop(); // 这个可以加，可以不加，效果一样，思路不同st.push(i);} else {while (heights[i] < heights[st.peek()]) { // 注意是whileint mid = st.peek();st.pop();int left = st.peek();int right = i;int w = right - left - 1;int h = heights[mid];result = Math.max(result, w * h);}st.push(i);}}return result;}
}