本文主要是介绍day49 | 42. 接雨水 84. 柱状图中最大的矩形,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码随想录算法训练营第 49 天| 42. 接雨水 84. 柱状图中最大的矩形
Leetcode 42. 接雨水
题目链接:https://leetcode.cn/problems/trapping-rain-water/description/
题目描述:
给定 n
个非负整数表示每个宽度为 1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
思路:
单调栈
代码:
class Solution {public int trap(int[] height) {int sum = 0;for (int i = 0; i < height.length; i++) {// 第一个柱子和最后一个柱子不接雨水if (i==0 || i== height.length - 1) continue;int rHeight = height[i]; // 记录右边柱子的最高高度int lHeight = height[i]; // 记录左边柱子的最高高度for (int r = i+1; r < height.length; r++) {if (height[r] > rHeight) rHeight = height[r];}for (int l = i-1; l >= 0; l--) {if(height[l] > lHeight) lHeight = height[l];}int h = Math.min(lHeight, rHeight) - height[i];if (h > 0) sum += h;}return sum;}
}
Leetcode 84. 柱状图中最大的矩形
题目链接:https://leetcode.cn/problems/largest-rectangle-in-histogram/description/
题目描述:
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4]
输出: 4
提示:
1 <= heights.length <=105
0 <= heights[i] <= 104
思路:单调栈
代码:
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 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;}
}
esult = Math.max(result, w * h);
}
st.push(i);
}
}
return result;
}
}
###### ######
这篇关于day49 | 42. 接雨水 84. 柱状图中最大的矩形的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!