代码随想录算法训练营第四十六天-42接雨水、84柱状图中最大的矩形

• 前言
  状态：42 看解析。84 看解析。

• 更新

24-07-13 初始记录
24-07-16 完成

初步题解

42 接雨水

题目链接：(https://leetcode.cn/problems/trapping-rain-water/)

84 柱状图中最大的矩形

题目链接：(https://leetcode.cn/problems/largest-rectangle-in-histogram)

看解析

42 接雨水

解析：(https://programmercarl.com/0042.接雨水.html)

1. 当前高度小于等于栈顶高度，入栈，指针后移。

2. 当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。

public int trap(int[] height) {  
    Stack<Integer> stack = new Stack<>();  
  
    int area = 0;  
  
    stack.push(0);  
    for (int i = 1; i < height.length; i++) {  
        if (height[i] <= height[stack.peek()]) {  
            stack.push(i);  
        } else {  
            // 当前元素小于栈顶元素  
            if (height[stack.peek()] >= height[i]) {  
                stack.push(i);  
            } else {  
                while (!stack.isEmpty() && height[i] > height[stack.peek()]) {  
                    // 当前的栈顶  
                    Integer mid = stack.pop();  
                    if (!stack.isEmpty()) {  
                        int h = Math.min(height[stack.peek()], height[i]) - height[mid];  
                        int w = i - stack.peek() - 1;  
                        area += h * w;  
                    }  
                }  
                stack.push(i);  
            }  
        }  
    }  
    return area;  
}

84 柱状图中最大的矩形

解析：(https://programmercarl.com/0084.柱状图中最大的矩形.html)

本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序

public int largestRectangleArea(int[] heights) {  
    Stack<Integer> stack = new Stack<>();  
    // 首末尾加零防止无法进入循环  
    int[] newHeights = new int[heights.length + 2];  
    for (int i = 1; i < newHeights.length - 1; i++) {  
        newHeights[i] = heights[i - 1];  
    }  
    newHeights[heights.length + 1] = 0;  
    newHeights[0] = 0;  
  
    int area = 0;  
    stack.push(0);  
    for (int i = 0; i < newHeights.length; i++) {  
        while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {  
            // 当前元素的前一个元素  
            Integer mid = stack.pop();  
            // 右侧数据与左侧数据的差值  
            int w = i - stack.peek() - 1;  
            area = Math.max(area, w * newHeights[mid]);  
        }  
        stack.push(i);  
    }  
  
    return area;  
}