代码随想录算法刷题训练营day49：LeetCode(42)接雨水、LeetCode(84)柱状图中最大的矩形
代码随想录算法刷题训练营day49：LeetCode(42)接雨水、LeetCode(84)柱状图中最大的矩形
LeetCode(42)接雨水
题目
代码
import java.util.Stack;class Solution {public int trap(int[] height) {//用单调栈进行操作int sum=0;Stack<Integer> stack=new Stack<>();for(int i=0;i<height.length;i++){if(stack.isEmpty()){stack.push(i);}else{while(!stack.isEmpty()&&height[i]>height[stack.peek()]){int maxRight=i;int middle=stack.peek();stack.pop();if(!stack.isEmpty()){int maxLeft=stack.peek();//计算面积int tempHeight=0;if(height[maxRight]>height[maxLeft]){tempHeight=height[maxLeft]; }else{tempHeight=height[maxRight];}sum=sum+(tempHeight-height[middle])*(maxRight-maxLeft-1);//这里是减1}}stack.push(i);}}return sum;}
}
LeetCode(84)柱状图中最大的矩形
题目
代码
import java.util.Stack;class Solution {public int largestRectangleArea(int[] heights) {int maxArea=0;//最大面积，单调递减栈+首尾得增加两个0int[] dateHeight=new int[heights.length+2];dateHeight[0]=0;dateHeight[dateHeight.length-1]=0;for(int i=0;i<heights.length;i++){dateHeight[i+1]=heights[i];}Stack<Integer> stack=new Stack<>();//单调递减栈for(int i=0;i<dateHeight.length;i++){if(stack.isEmpty()){stack.push(i);}else{while (!stack.isEmpty()&&dateHeight[i]<dateHeight[stack.peek()]) {int rightMin=i;int mid=stack.peek();stack.pop();if(!stack.isEmpty()){int leftMin=stack.peek();if((rightMin-leftMin-1)*dateHeight[mid]>maxArea){maxArea=(rightMin-leftMin-1)*dateHeight[mid];}}}stack.push(i);}}return maxArea;}
}