代码随想录day42：单调栈part2

42. 接雨水

class Solution {public int trap(int[] height) {int ans = 0;Deque<Integer> st = new ArrayDeque<>();for(int i = 0; i < height.length; i++){while(!st.isEmpty() && height[i] >= height[st.peek()]){int mid = height[st.pop()];if(st.isEmpty()) break;int left = height[st.peek()];int right = height[i];int h = Math.min(right,left) - mid;ans += h * (i - st.peek() - 1);}st.push(i);}return ans;}
}

84. 柱状图中最大的矩形

class Solution {public int largestRectangleArea(int[] heights) {Deque<Integer> st = new ArrayDeque<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 = 0; i < heights.length; i++) {while (!st.isEmpty() && heights[i] <= heights[st.peek()]) { // 注意是whileint mid = st.peek();st.pop();if(!st.isEmpty()){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;}
}

这两个题一个代码格式，接雨水是找遍历位置两边比他大的，最大面积是找两边比他小的