本文主要是介绍Day43 | 42. 接雨水 84.柱状图中最大的矩形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
语言
Java
42. 接雨水
接雨水
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
思路
本题可以用暴力的方法做，也可以用双指针做，但是本次我们使用单调栈完成
定义一个栈用来存递增的高度。先将放进去一个元素。
定义一个sum 用来最后返回结果。
定义stackTop表示栈顶元素
循环比较栈顶元素和当前循环遍历的元素
如果当前元素小，直接加入栈中
相等的话，先弹出，再加入栈中，这样能减少操作。
如果栈顶元素小，判断如果栈不为空的情况下，利用底乘高来计算雨水面积
底部：当前索引位置减去栈顶索引位置 - 1
高度：左侧高度和右边取最小 - 当前高度
将底乘高加入 sum中，然后将当前元素放到栈内
最后返回结果sum.
代码
class Solution {public int trap(int[] height) {int size = height.length;if (size <= 2) return 0;Stack<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]) {stack.pop();stack.push(index);} else {int 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;}
}易错点
三种判断情况要理清楚
底乘高要大于零的情况下再加到sum中
84.柱状图中最大的矩形
柱状图中最大的矩形
题目
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
思路
本题的大体思路与接雨水相差不多，栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度。
- 情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
- 情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
- 情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
具体细节看代码。
代码
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;}
}易错点
需要在数组的开始和结尾都加0.
总结
单调栈今天就结束了，这两道题还是非常有难度的，不愧为经典的hard题。
明天图论继续加油！
立志不坚，终不济事
这篇关于Day43 | 42. 接雨水 84.柱状图中最大的矩形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
