代码随想录打卡第60天|84.柱状图中最大的矩形（本轮打卡圆满结束啦~）

84.柱状图中最大的矩形(与接雨水类似）

关键点1：先前的一些准备

单调栈：单调栈的含义->用栈记录已经遍历过的元素，再将0元素压入栈

结果：sum，初始化为0

关键点2：核心部分

for循环遍历给定数组：有三种情况

情况1：heights_new[i] > heights_new[st.peek()]代表heights_new[i]大于栈里的值对应数组数值的情况，那此刻将i再压入栈中st.push(i);

情况2：heights_new[i] == heights_new[st.peek()]代表：heights_new[i]等于栈里的值对应数组数值的情况，那此刻将栈内元素弹出，再将i压入栈中 st.pop();  st.push(i);

情况3：!st.isEmpty() && heights_new[i] < heights_new[st.peek()]代表heights_new[i]小于栈里的值对应数组数值的情况，那此刻则找到了小于栈顶数字位置对应数值的元素为 heights_new[i] ，对应的位置为i,

3-1：记录栈里这个值mid = st.peek();

3-2：弹出栈内比i大的那个数，此时栈内剩下的这个数，就是原来mid左边比mid小的那个数（栈内是递减的）

3-3：再判断栈是否为空if(!st.isEmpty())，求解h与w
int h = heights_new[mid]
//w = 右边的横坐标-左边的横坐标-1
int w = i - st.peek() - 1;
sum =Math.max( h*w, sum);

3-4：当结束while循环，则将此时 heights_new[i]的这个i再压入栈中st.push(i);

关键点3：结果

返回sum就行

class Solution {public int largestRectangleArea(int[] heights) {Stack<Integer> st = new Stack<>();st.push(0);int sum = 0;int[] heights_new = new int[heights.length+2];heights_new[0] = 0;heights_new[heights_new.length-1] = 0;for(int i = 0; i < heights.length;i++){heights_new[i+1] = heights[i];}for(int i = 1;i < heights_new.length;i++){if(heights_new[i] > heights_new[st.peek()]){st.push(i);}else if(heights_new[i] == heights_new[st.peek()]){st.pop();st.push(i);}else{while(!st.isEmpty() && heights_new[i] < heights_new[st.peek()]){int mid = st.peek();st.pop();if(!st.isEmpty()){int h = heights_new[mid];int w = i - st.peek() - 1;sum = Math.max(h*w , sum);}}st.push(i);}}return sum;}
}