代码随想录Day49 42. 接雨水，84.柱状图中最大的矩形。

1.接雨水

力扣题目链接(opens new window)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

• 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
• 输出：6
• 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

• 输入：height = [4,2,0,3,2,5]
• 输出：9

思路

接雨水问题在面试中还是常见题目的，有必要好好讲一讲。

本文深度讲解如下三种方法：

• 暴力解法
• 双指针优化
• 单调栈

暴力解法

本题暴力解法也是也是使用双指针。

首先要明确，要按照行来计算，还是按照列来计算。

按照行来计算如图： 

按照列来计算如图： 

一些同学在实现的时候，很容易一会按照行来计算一会按照列来计算，这样就会越写越乱。

我个人倾向于按照列来计算，比较容易理解，接下来看一下按照列如何计算。

首先，如果按照列来计算的话，宽度一定是1了，我们再把每一列的雨水的高度求出来就可以了。

可以看出每一列雨水的高度，取决于，该列 左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。

这句话可以有点绕，来举一个理解，例如求列4的雨水高度，如图：

列4 左侧最高的柱子是列3，高度为2（以下用lHeight表示）。

列4 右侧最高的柱子是列7，高度为3（以下用rHeight表示）。

列4 柱子的高度为1（以下用height表示）

那么列4的雨水高度为 列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height。

列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了。

此时求出了列4的雨水体积。

一样的方法，只要从头遍历一遍所有的列，然后求出每一列雨水的体积，相加之后就是总雨水的体积了。

首先从头遍历所有的列，并且要注意第一个柱子和最后一个柱子不接雨水。

双指针优化

在暴力解法中，我们可以看到只要记录左边柱子的最高高度 和 右边柱子的最高高度，就可以计算当前位置的雨水面积，这就是通过列来计算。

当前列雨水面积：min(左边柱子的最高高度，记录右边柱子的最高高度) - 当前柱子高度。

为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍，这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上（maxLeft），右边最高高度记录在一个数组上（maxRight），这样就避免了重复计算。

当前位置，左边的最高高度是前一个位置的左边最高高度和本高度的最大值。

即从左向右遍历：maxLeft[i] = max(height[i], maxLeft[i - 1]);

从右向左遍历：maxRight[i] = max(height[i], maxRight[i + 1]);

单调栈解法

关于单调栈的理论基础，单调栈适合解决什么问题，单调栈的工作过程，大家可以先看这题讲解 739. 每日温度 (opens new window)。

单调栈就是保持栈内元素有序。和栈与队列：单调队列 (opens new window)一样，需要我们自己维持顺序，没有现成的容器可以用。

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

而接雨水这道题目，我们正需要寻找一个元素，右边最大元素以及左边最大元素，来计算雨水面积。

#准备工作

那么本题使用单调栈有如下几个问题：

1. 首先单调栈是按照行方向来计算雨水，如图：

知道这一点，后面的就可以理解了。

1. 使用单调栈内元素的顺序

从大到小还是从小到大呢？

从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。

因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。

如图：

关于单调栈的顺序给大家一个总结： 739. 每日温度 (opens new window)中求一个元素右边第一个更大元素，单调栈就是递增的，84.柱状图中最大的矩形 (opens new window)求一个元素右边第一个更小元素，单调栈就是递减的。

1. 遇到相同高度的柱子怎么办。

遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。

例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出，把第二个5添加到栈中。

因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。

如图所示：

1. 栈里要保存什么数值

使用单调栈，也是通过 长 * 宽 来计算雨水面积的。

长就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算，

那么栈里有没有必要存一个pair<int, int>类型的元素，保存柱子的高度和下标呢。

其实不用，栈里就存放下标就行，想要知道对应的高度，通过height[stack.top()] 就知道弹出的下标对应的高度了。

单调栈处理逻辑

以下操作过程其实和 739. 每日温度 (opens new window)也是一样的，建议先做 739. 每日温度 (opens new window)。

以下逻辑主要就是三种情况

• 情况一：当前遍历的元素（柱子）高度小于栈顶元素的高度 height[i] < height[st.top()]
• 情况二：当前遍历的元素（柱子）高度等于栈顶元素的高度 height[i] == height[st.top()]
• 情况三：当前遍历的元素（柱子）高度大于栈顶元素的高度 height[i] > height[st.top()]

先将下标0的柱子加入到栈中，st.push(0);。 栈中存放我们遍历过的元素，所以先将下标0加进来。

然后开始从下标1开始遍历所有的柱子，for (int i = 1; i < height.size(); i++)。

如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。

如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。

如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了，如图所示：

取栈顶元素，将栈顶元素弹出，这个就是凹槽的底部，也就是中间位置，下标记为mid，对应的高度为height[mid]（就是图中的高度1）。

此时的栈顶元素st.top()，就是凹槽的左边位置，下标为st.top()，对应的高度为height[st.top()]（就是图中的高度2）。

当前遍历的元素i，就是凹槽右边的位置，下标为i，对应的高度为height[i]（就是图中的高度3）。

此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的元素，三个元素来接水！

那么雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度，代码为：int h = min(height[st.top()], height[i]) - height[mid];

雨水的宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度），代码为：int w = i - st.top() - 1 ;

当前凹槽雨水的体积就是：h * w。

暴力解法

public class Trapping_Rain_Water {
    public int trap1(int[] height) {
        int sum = 0;//sum变量用来存储可以接的雨水总量。
        for (int i = 0; i < height.length; i++) {//遍历数组中的每个元素。
            if (i==0 || i== height.length - 1) continue;//对于每个元素，先向右遍历找到比当前元素高的最高的右侧高度rHeight。
            int rHeight = height[i];
            int lHeight = height[i];//再向左遍历找到比当前元素高的最高的左侧高度lHeight。
            for (int r = i+1; r < height.length; r++) {
                if (height[r] > rHeight) rHeight = height[r];
            }
            for (int l = i-1; l >= 0; l--) {
                if(height[l] > lHeight) lHeight = height[l];
            }
            int h = Math.min(lHeight, rHeight) - height[i];//使用min(lHeight, rHeight) - height[i]计算当前位置可以接的雨水量，并累加到sum中。
            if (h > 0) sum += h;
        }
        return sum;
    }
  
}

• 时间复杂度：O(n^2)，其中n是数组height的长度。这是因为有两个嵌套循环，外层循环遍历每个元素，内层循环分别向左和向右遍历。
• 空间复杂度：O(1)，除了输入数组外，没有使用额外的空间。

双指针

public class Trapping_Rain_Water {
    
    public int trap2(int[] height) {
        int length = height.length;
        if (length <= 2) return 0;
        int[] maxLeft = new int[length];//maxLeft数组存储每个位置左侧的最高高度。
        int[] maxRight = new int[length];//maxRight数组存储每个位置右侧的最高高度。
        maxLeft[0] = height[0];
        for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);//从左到右填充maxLeft数组。
        maxRight[length - 1] = height[length - 1];
        for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);//从右到左填充maxRight数组。
        int sum = 0;//sum变量用来存储可以接的雨水总量。
        for (int i = 0; i < length; i++) {//对于每个位置，计算min(maxLeft[i], maxRight[i]) - height[i]，如果结果大于0，则累加到sum中。
            int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
            if (count > 0) sum += count;
        }
        return sum;
    }
  
}

• 时间复杂度：O(n)，其中n是数组height的长度。这是因为每个元素只被访问了常数次。
• 空间复杂度：O(n)，因为使用了两个额外的数组maxLeft和maxRight来存储每个位置左侧和右侧的最高高度。

public class Trapping_Rain_Water {
   
    public int trap3(int[] height) {
        if (height.length <= 2) {
            return 0;
        }//maxLeft和maxRight分别初始化为数组的第一个元素和最后一个元素。
        int maxLeft = height[0], maxRight = height[height.length - 1];
        int l = 1, r = height.length - 2;//l和r分别初始化为数组的开始和结束索引。
        int res = 0;//res变量用来存储可以接的雨水总量。
        while (l <= r) {//当l小于等于r时，比较maxLeft和maxRight，将较小的高度与当前高度比较，计算雨水量并累加到res中。
            maxLeft = Math.max(maxLeft, height[l]);
            maxRight = Math.max(maxRight, height[r]);
            if (maxLeft < maxRight) {
                res += maxLeft - height[l ++];//根据比较结果，移动l或r指针。
            } else {
                res += maxRight - height[r --];
            }
        }
        return res;
    }
   
}

• 时间复杂度：O(n)，与trap2方法相同，每个元素只被访问了常数次。
• 空间复杂度：O(1)，除了输入数组外，没有使用额外的空间。

单调栈

public class Trapping_Rain_Water {
   
    public int trap4(int[] height){
        int size = height.length;
        if (size <= 2) return 0;
        Stack<Integer> stack = new Stack<Integer>();//stack用来存储索引。
        stack.push(0);
        int sum = 0;//sum变量用来存储可以接的雨水总量。
        for (int index = 1; index < size; index++){//遍历数组中的每个元素。
            int stackTop = stack.peek();
            if (height[index] < height[stackTop]){//如果当前元素的高度小于栈顶元素的高度，则将当前索引压入栈中。
                stack.push(index);
            }else if (height[index] == height[stackTop]){//如果当前元素的高度等于栈顶元素的高度，则弹出栈顶元素，并更新栈顶元素的索引。
                stack.pop();
                stack.push(index);
            }else{//如果当前元素的高度大于栈顶元素的高度，则执行以下操作：弹出栈顶元素，计算雨水量，并累加到sum中。更新栈顶元素的索引。
                int heightAtIdx = height[index];
                while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){
                    int mid = stack.pop();
                    if (!stack.isEmpty()){
                        int left = stack.peek();
                        int h = Math.min(height[left], height[index]) - height[mid];
                        int w = index - left - 1;
                        int hold = h * w;
                        if (hold > 0) sum += hold;
                        stackTop = stack.peek();
                    }
                }
                stack.push(index);
            }
        }

        return sum;
    }
}

• 时间复杂度：O(n)，与trap2和trap3方法相同，每个元素只被访问了常数次。
• 空间复杂度：O(n)，因为使用了额外的栈结构来存储索引。

2.柱状图中最大的矩形

力扣题目链接(opens new window)

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

• 1 <= heights.length <=10^5
• 0 <= heights[i] <= 10^4

思路

本题和42. 接雨水 (opens new window)，是遥相呼应的两道题目，建议都要仔细做一做，原理上有很多相同的地方，但细节上又有差异，更可以加深对单调栈的理解！

其实这两道题目先做那一道都可以，但我先写的42.接雨水的题解，所以如果没做过接雨水的话，建议先做一做接雨水，可以参考我的题解：42. 接雨水

双指针解法

本题双指针的写法整体思路和42. 接雨水 (opens new window)是一致的，但要比42. 接雨水 (opens new window)难一些。

难就难在本题要记录记录每个柱子 左边第一个小于该柱子的下标，而不是左边第一个小于该柱子的高度。

所以需要循环查找，也就是下面在寻找的过程中使用了while，详细请看下面注释，整理思路在题解：42. 接雨水 (opens new window)中已经介绍了。

单调栈

本地单调栈的解法和接雨水的题目是遥相呼应的。

为什么这么说呢，42. 接雨水 (opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。

这里就涉及到了单调栈很重要的性质，就是单调栈里的顺序，是从小到大还是从大到小。

在题解42. 接雨水 (opens new window)中我讲解了接雨水的单调栈从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。

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

我来举一个例子，如图：

只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

所以本题单调栈的顺序正好与接雨水反过来。

此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度

理解这一点，对单调栈就掌握的比较到位了。

除了栈内元素顺序和接雨水不同，剩下的逻辑就都差不多了，在题解42. 接雨水 (opens new window)我已经对单调栈的各个方面做了详细讲解，这里就不赘述了。

主要就是分析清楚如下三种情况：

• 情况一：当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
• 情况二：当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
• 情况三：当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况

在 height数组上后，都加了一个元素0， 为什么这么做呢？

首先来说末尾为什么要加元素0？

如果数组本身就是升序的，例如[2,4,6,8]，那么入栈之后 都是单调递减，一直都没有走 情况三 计算结果的哪一步，所以最后输出的就是0了。 如图：

那么结尾加一个0，就会让栈里的所有元素，走到情况三的逻辑。

开头为什么要加元素0？

如果数组本身是降序的，例如 [8,6,4,2]，在 8 入栈后，6 开始与8 进行比较，此时我们得到 mid（8），right（6），但是得不到 left。

（mid、left，right 都是对应版本一里的逻辑）

因为 将 8 弹出之后，栈里没有元素了，那么为了避免空栈取值，直接跳过了计算结果的逻辑。

之后又将6 加入栈（此时8已经弹出了），然后 就是 4 与 栈口元素 6 进行比较，周而复始，那么计算的最后结果result就是0。 如图所示：

所以我们需要在 height数组前后各加一个元素0。

暴力解法

public class Largest_Rectangle_in_Histogram {
    public int largestRectangleArea1(int[] heights) {
        int length = heights.length;
        int[] minLeftIndex = new int [length];//minLeftIndex数组存储每个柱子左侧最矮柱子的索引。
        int[] minRightIndex = new int [length];//minRightIndex数组存储每个柱子右侧最矮柱子的索引。
        minLeftIndex[0] = -1 ;
        for (int i = 1; i < length; i++) {//从左到右遍历heights，对于每个柱子，向左找到比它高的柱子的索引。
            int t = i - 1;
            while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
            minLeftIndex[i] = t;
        }
        minRightIndex[length - 1] = length;
        for (int i = length - 2; i >= 0; i--) {//从右到左遍历heights，对于每个柱子，向右找到比它高的柱子的索引。
            int t = i + 1;
            while(t < length && heights[t] >= heights[i]) t = minRightIndex[t];
            minRightIndex[i] = t;
        }
        int result = 0;
        for (int i = 0; i < length; i++) {//遍历heights，对于每个柱子，计算以它为高的矩形的宽度（minRightIndex[i] - minLeftIndex[i] - 1），并更新最大面积。
            int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
            result = Math.max(sum, result);
        }
        return result;
    }
   
}

• 时间复杂度：O(n)，其中n是heights数组的长度。这个方法需要三次遍历数组：一次从左到右，一次从右到左，以及一次计算面积。
• 空间复杂度：O(n)，因为创建了两个额外的数组minLeftIndex和minRightIndex来存储索引。

单调栈

public class Largest_Rectangle_in_Histogram {
    
    int largestRectangleArea2(int[] heights) {
        Stack<Integer> st = new Stack<Integer>();//st栈用来存储柱子的索引。
        int [] newHeights = new int[heights.length + 2];//将heights数组扩展，两端添加0，以便处理边界情况。
        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;
        for (int i = 1; i < heights.length; i++) {//对于每个柱子，如果当前柱子高于栈顶柱子，则将当前索引压入栈中。
            if (heights[i] > heights[st.peek()]) {
                st.push(i);
            } else if (heights[i] == heights[st.peek()]) {//如果当前柱子等于栈顶柱子，则弹出栈顶元素，并更新栈顶元素的索引。
                st.pop();
                st.push(i);
            } else {//如果当前柱子低于栈顶柱子，则弹出栈顶元素，计算以栈顶元素为高的矩形的面积，并更新最大面积。
                while (heights[i] < heights[st.peek()]) {
                    int mid = st.peek();
                    st.pop();
                    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;
    }
   
}

• 时间复杂度：O(n)，其中n是heights数组的长度。这个方法需要一次遍历数组，并且在最坏情况下，每个元素都会被压入和弹出栈一次。
• 空间复杂度：O(n)，因为创建了一个栈st来存储索引，并且创建了一个新数组newHeights来扩展原数组。

public class Largest_Rectangle_in_Histogram {
        public int largestRectangleArea3(int[] heights) {
        int[] newHeight = new int[heights.length + 2];// 创建一个新的数组newHeight，其长度比原数组heights长2，以便在数组的两端添加0。
        System.arraycopy(heights, 0, newHeight, 1, heights.length);//使用System.arraycopy方法将heights数组的内容复制到newHeight数组中，从索引1开始。
        newHeight[heights.length+1] = 0;//在newHeight数组的两端添加0，这样处理的目的是为了简化算法，使得在处理数组时不需要单独处理边界情况。
        newHeight[0] = 0;
        Stack<Integer> stack = new Stack<>();//创建一个栈stack，用于存储索引。
        stack.push(0);//将索引0（即newHeight数组的第一个元素）压入栈中，因为数组两端都是0，所以从索引0开始是合理的。
        int res = 0;
        for (int i = 1; i < newHeight.length; i++) {//从索引1开始遍历newHeight数组，直到数组的末尾。
            while (newHeight[i] < newHeight[stack.peek()]) {//在遍历过程中，使用栈来维护一个递增序列，即栈中的元素对应的newHeight值是递增的。
                int mid = stack.pop();//如果当前索引i对应的高度小于栈顶元素对应的高度，说明我们找到了一个局部最小值，可以计算以栈顶元素为高的矩形面积。弹出栈顶元素，这个元素对应的索引mid就是局部最小值的索引。
                int w = i - stack.peek() - 1;//计算宽度w，即从栈顶元素的下一个索引到当前索引i的距离减1。
                int h = newHeight[mid];//获取高度h，即栈顶元素对应的高度。
                res = Math.max(res, w * h);//更新最大面积res，取w * h和当前最大面积res的较大值。
            }
            stack.push(i);//将当前索引i压入栈中，以便后续计算可能的更大矩形面积。
        }
        return res;
    }
}

• 时间复杂度：O(n)，其中n是heights数组的长度。这个方法需要一次遍历数组，并且在最坏情况下，每个元素都会被压入和弹出栈一次。
• 空间复杂度：O(n)，因为创建了一个栈stack来存储索引，并且创建了一个新数组newHeight来扩展原数组。