思路：
本题首先我实现的思路使用暴力解法 ，虽说是暴力， 但是复杂度却是和 使用单调栈相差无几的。
根据示例1 中的这张图
首先想到的是如何计算这个雨水的面积？ 横向还是纵向 ？
一个单位的雨水也就是相当于一个正方体的体积 ，我们要做的就是数正方体的个数 ，这里我们只需要考虑平面即可。同时因为横向的边长都是固定的1 ， 所以这里我们通过纵向来进行计算， 也就是按照列来计算。 算出每一列的有效雨水面积，然后累加即可得到整体的面积。
通过上述的描述， 我们知道了整体的思路 ，接下来就是具体的实现思路 。
循环遍历每个柱子，找出每个柱子最左边 和 最右边的边界（也就是左右两边第一个比当前柱子高的柱子）
这里需要注意的是， 我们第一个柱子 和 最后一个柱子是不能计算的，他们充当最后的边界
因为我们是按列进行累加的 ，同时每个柱子的宽度都是 1 ， 所以只需要算出列左右两边最短的列高 - 当前列高即可得到雨水的高。 也就可以得到雨水的体积。
实现：
上述步骤中的，第一步如果我们使用暴力解法的话， 也就是循环遍历每个柱子， 然后得到每个柱子的边界， 然后使用一个变量来接收 ，这样的作法虽然没错， 但是超时了 ，所以我们采用的是使用两个数组来接收每个柱子的边界，也同样单调栈的思路 : 通过空间换时间。 可以pass
class Solution { public int trap(int[] height) { //使用数组来记录每个节点的最大左右边界 int[] maxLeft = new int[height.length]; int[] maxRight = new int[height.length]; int sum =0 ; //获取每柱子的最高左边界 maxLeft[0] = height[0]; for(int i =1; i<height.length;i++){ maxLeft[i] = Math.max(height[i], maxLeft[i-1]); } //获取每个柱子的最高右边界 maxRight[maxRight.length- 1] = height[height.length - 1]; for(int i = maxRight.length - 2 ; i>= 0; i--){ maxRight[i] = Math.max(height[i], maxRight[i+1]); } // 得到每个柱子容纳的水 ，然后添加 for(int i =0 ;i < height.length;i++){ sum += Math.min(maxRight[i], maxLeft[i]) - height[i]; } return sum; } /** 双指针法， 最后超时 public int trap(int[] height) { int sum =0 ; for(int i =0 ; i< height.length;i++){ //定义左右边界 int lheight = height[i]; int rheight = height[i]; // 寻找左右边界 for(int j = i+1; j <height.length;j++){ rheight = Math.max(rheight,height[j]); } for(int j = i-1; j >=0 ; j--){ lheight = Math.max(lheight, height[j]); } //得到当前柱子能够容纳的雨水 int h = Math.min(lheight,rheight) - height[i]; if(h >0 ){ sum += h; } } return sum; } */ }
单调栈实现
class Solution { public int trap(int[] height) { //使用单调栈实现 int sum = 0; Stack<Integer> st = new Stack<>(); st.push(0); // 添加第一个索引 for(int i = 1;i < height.length; i++){ if(height[st.peek()] > height[i]){ st.push(i); } if(height[st.peek()] == height[i]){ //先弹出栈顶元素， 然后再入栈当前元素 st.pop(); st.push(i); }else{ //如果栈顶的元素 < 当前元素 ，那么就需要弹出栈顶元素， 然后当前元素入栈 while(!st.isEmpty() && height[st.peek()] < height[i]){ int mid = st.peek(); st.pop(); if(!st.isEmpty()){ //之前的栈顶元素为柱子 。当前栈顶元素为它的左边界， 当前元素为它的右边界 int h = Math.min(height[i], height[st.peek()]) - height[mid]; int w = i - st.peek() - 1; sum += h * w; } } st.push(i); } } return sum; } }
84 柱形图中的最大矩形
题目:
给定 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 { public int largestRectangleArea(int[] heights) { //通过空间换时间的方法 int minLeft[] = new int[heights.length]; int minRight[] = new int[heights.length]; int sum = 0; //找左边比当前元素小的 minLeft[0]= -1; for(int i =1 ;i< heights.length;i++){ int t = i - 1; //找到并且为每个元素赋值 while(t>= 0 && heights[t] >= heights[i]){ t = minLeft[t]; } minLeft[i] = t; } //找到右两边第一个小于当前柱子的值 minRight[minRight.length - 1] = minRight.length ; for(int i = minRight.length - 2; i>= 0 ;i--){ int t = i + 1; while(t <= minRight.length-1 && heights[i] <= heights[t]){ t = minRight[t]; } minRight[i] = t; } //计算得到每个柱子的最大面积 for(int i =0 ;i <heights.length; i++){ int weight = minRight[i] - minLeft[i] -1; int height = heights[i]; sum = Math.max(sum, weight * height); } return sum; } /** public int largestRectangleArea(int[] heights) { //暴力解法 int sum = 0; for(int i= 0 ;i <heights.length; i++){ //找到左右两边第一个小于当前柱子的值 int left = i; int right = i; for(; left >=0 ;left--){ if(heights[left] < heights[i] ) break; } for(; right < heights.length; right++){ if(heights[right] < heights[i]) break; } //算出当前柱子的宽度 int weight = right - left - 1; int height = heights[i]; sum = Math.max(sum, weight * height); } return sum; } */ }
class Solution { public int largestRectangleArea(int[] heights) { // 数组扩容，在头和尾各加入一个元素 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; int res = 0 ; Stack<Integer> st = new Stack<>(); st.push(0); for(int i =1; i < heights.length ;i++){ //如果栈顶元素 < 当前元素 if(heights[st.peek()] < heights[i]){ st.push(i); }if(heights[i] == heights[st.peek()]){ st.pop(); st.push(i); }else{ while(!st.isEmpty() && heights[st.peek()] > heights[i]){ int mid = st.pop(); //找到当前元素作为中间 if(!st.isEmpty()){ 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; } }
