代码随想录算法训练营 | 42. 接雨水，84. 柱状图中最大的矩形

42. 接雨水
题目链接：42. 接雨水
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰接雨水
日期：2024-10-21

Java代码如下：

class Solution {public int trap(int[] height){int size = height.length;if (size <= 2) return 0;Deque<Integer> st = new LinkedList<>();st.push(0);int sum = 0;for (int i = 1; i < size; i++){if (height[i] < height[st.peek()]){st.push(i);}else if (height[i] == height[st.peek()]){st.pop();st.push(i);}else{while (!st.isEmpty() && (height[i] > height[st.peek()])){int mid = st.pop();if (!st.isEmpty()){int left = st.peek();int h = Math.min(height[left], height[i]) - height[mid];int w = i - left - 1;int hold = h * w;if (hold > 0) sum += hold;}}st.push(i);}}return sum;}
}

84. 柱状图中最大的矩形
题目链接：84. 柱状图中最大的矩形
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰柱状图中最大的矩形
日期：2024-10-21

Java代码如下：

class Solution {int largestRectangleArea(int[] heights) {Stack<Integer> st = new Stack<Integer>();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 res = 0;for (int i = 1; i < heights.length; i++) {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()]) {int mid = st.peek();st.pop();int left = st.peek();int right = i;int w = right - left - 1;int h = heights[mid];res = Math.max(res, w * h);}st.push(i);}}return res;}
}