Day49 ＞＞ 42. 接雨水 + 84.柱状图中最大的矩形

代码随想录-单调栈Part2

42. 接雨水

class Solution { public int trap(int[] height) { if (height.length <= 2) { return 0; } int maxLeft = height[0], maxRight = height[height.length - 1]; int l = 1, r = height.length - 2; int res = 0; while (l <= r) { maxLeft = Math.max(maxLeft, height[l]); maxRight = Math.max(maxRight, height[r]); if (maxLeft < maxRight) { res += maxLeft - height[l ++]; } else { res += maxRight - height[r --]; } } return res; } }

84.柱状图中最大的矩形

class Solution { public int largestRectangleArea(int[] heights) { int[] newHeight = new int[heights.length + 2]; System.arraycopy(heights, 0, newHeight, 1, heights.length); newHeight[heights.length+1] = 0; newHeight[0] = 0; Stack<Integer> stack = new Stack<>(); stack.push(0); int res = 0; for (int i = 1; i < newHeight.length; i++) { while (newHeight[i] < newHeight[stack.peek()]) { int mid = stack.pop(); int w = i - stack.peek() - 1; int h = newHeight[mid]; res = Math.max(res, w * h); } stack.push(i); } return res; } }