【算法题解】21. 单调栈求解 “柱状图中最大的矩形”

青旅半醒 2024-03-26 22:14 125阅读 0赞

#### 文章目录 ####

*   *  题目
     *  暴力解法
     *   *  代码实现
         *   *  Java
             *  Go
         *  复杂度分析
     *  单调栈
     *   *  代码实现
         *   *  Java
             *  Go
         *  复杂度分析

> 这是一道 困难 题
> 
> 题目来自：https://leetcode.cn/problems/largest-rectangle-in-histogram

### 题目 ###

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

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

**示例 1:**

![106b7c6799f8d29d0944a05d8cfb7fd0.jpeg][]

输入：heights = [2,1,5,6,2,3] 
    输出：10 解释：最大的矩形为图中红色区域，面积为 10

**示例 2：**

![6106bd12ba09f66431310c5fcf15adbb.jpeg][]

输入： heights = [2,4] 
    输出： 4

**提示：**

*   1 < = h e i g h t s . l e n g t h < = 1 0 5 1 <= heights.length <=10^5 1<=heights.length<=105
 *   0 < = h e i g h t s \[ i \] < = 1 0 4 0 <= heights\[i\] <= 10^4 0<=heights\[i\]<=104

### 暴力解法 ###

核心思想就是获取每个柱子的**左右边界**。

如下图所示：

第 `3` 个柱子左边界 `left = 3`, 右边界 `right = 4`，高度 `height = 5`，能够勾勒出的最大矩形面积为 （`4 - 3 + 1）* 5 = 10`。

![04c6b007c9ff4df342b696c71a348c04.png][]

第 `5` 个柱子左边界 `left = 3`, 右边界 `right = 6`，高度 `height = 2`，能够勾勒出的最大矩形面积为 （`6 - 3 + 1）* 2 = 8`。

循环遍历每个柱子，并计算其勾勒出的最大面积。最后在这些结果中取最大的一个。

#### 代码实现 ####

##### Java #####

class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            int n = heights.length;
            int ans = 0;
            for(int i = 0; i < n; i++){
        
                int left = i, right = i, height = heights[i];
                while(left - 1 >= 0 && heights[left - 1] >= height){
        
                    left--;
                }
                while(right + 1 < n && heights[right + 1] >= height){
        
                    right++;
                }
                ans = Math.max(ans, (right - left + 1) * height);
            }
    
            return ans;
    
        }
    }

##### Go #####

func largestRectangleArea(heights []int) int {
        
        n := len(heights)
        ans := 0
        for i := 0; i < n; i++ {
        
            left, right := i, i
             for left - 1 >= 0 && heights[left - 1] >= heights[i] {
        
                 left--;
             }
             for right + 1 < n && heights[right + 1] >= heights[i] {
        
                 right++;
             }
            ans = max(ans, (right - left + 1) * heights[i])
        } 
        return ans
    }
    
    func max(a int, b int) int {
        
        if a > b {
        
            return a
        }
    
        return b
    }

#### 复杂度分析 ####

时间复杂度： O ( N 2 ) O(N^2) O(N2)，外层循环 `n` 次，内层循环每次最多 `n` 次。

空间复杂度： O ( 1 ) O(1) O(1)。

### 单调栈 ###

暴力解法的时间复杂度为 O ( N 2 ) O(N^2) O(N2)，**数据超过一定量的时候会超时**。我们需要想办法对其进行优化。

我们先考虑一种特殊情况，就是给出的每个柱子的高度都是单调递增的，如下图所示：

![5f13987d21b77ed683474eb24e36eba0.png][]

那么，每个柱子的左右边界就都是确定的：左边界就是自己的编号 `i` , 右边界就是最右边的最高的那个柱子 `n` 。

对应到代码里，即 `left = i,` `right = n - 1`，内层寻找左右边界的 `while` 循环就可以省略掉。

以Java代码为例：

class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            int n = heights.length;
            int ans = 0;
            for(int i = 0; i < n; i++){
        
                int left = i, right = n - 1, height = heights[i];
                ans = Math.max(ans, (right - left + 1) * height);
            }
    
            return ans;
    
        }
    }

而实际情况显然不是上述的单调递增的，但我们可以将实际情况看成是**在单调递增的情况下，出现的一个特殊情况。**

如下图所示：

![f62054583cf045a5089417a024a713f4.png][]

1.  当第 `5` 个柱子出现的时候，破坏了单调递增的特性。
2.  那么对于第 `4` 个柱子来说，其左右边界就都是 `4`，因为其左边和右边的柱子都比它矮。其能够勾勒出的最大矩形面积肯定就是其本身的高度。这时我们把第 `4` 个柱子的最大面积记录下来作为备选答案，然后将第 `4` 个柱子删掉，并将其宽度合并到第 `3` 个柱子和第 `5` 个柱子中的高的那个上，因为最高的那个柱子的宽度会影响所有柱子的答案。
3.  因为第 `3` 个柱子的高度任然比第 `5` 个柱子要高，所以依然不满足单调递增。这个时候第 `3` 个柱子能勾勒出的最大面积其实也已经确定，同计算第 `4` 个柱子是一样的，需要注意的一点就是第 `3` 个柱子的宽度已经不是 `1` 了。
4.  如果前面还有其他柱子的高度高于第 `5` 个柱子，同样需要计算其最大面积作为备选答案后将其删掉，并将其宽度合并的前一个和新增柱子中高的那个上，直到最后前面所有的柱子都没有新增的柱子高了，加入新增的柱子。
5.  当新增的柱子和当前最高的柱子一样高的时候，直接将最后一个柱子的宽度加 `1` 。
6.  最终得到的是一个单调递增的柱状图，计算其中每一个的最大面积，并和之前删掉的柱子的备用答案一起求最大值，

上面的思路总结起来其实就是：

1.  当遇到更高的柱子就加入。
2.  当遇到矮了的柱子就将之前加入的那些更高的柱子以 **后进先出** 的顺序依次计算答案后删掉。

看到 **后进先出**，自然而然就想到用 **栈** 来实现上面思路了。

#### 代码实现 ####

栈中存放的元素是一个数组，数组中存放柱子的宽度和高度。

这里有个小技巧，可以在给定的数组后面再加一个高度为 `0`的柱子 ，在不影响结果的情况下，可以直接将栈清空。

##### Java #####

class Solution {
        
    
        private Deque<int[]> stack = new LinkedList<>();
    
        public int largestRectangleArea(int[] heights) {
        
            int n = heights.length;
            int ans = 0, width = 0;
            // {宽度， 高度}
            for(int i = 0; i <= n; i++){
        
                int height = 0;
                if(i < n){
        
                    height = heights[i];
                }
                if(stack.isEmpty()){
        
                    stack.push(new int[]{
        1, height});
                    continue;
                }
                if(height == stack.peek()[1]){
        
                    stack.peek()[0] = stack.peek()[0] + 1;
                    continue;
                }
    
                if(height > stack.peek()[1]){
        
                    stack.push(new int[]{
        1, height});
                    continue;
                }
    
                width = 0;
                while(!stack.isEmpty() && height < stack.peek()[1]){
        
                    int[] top = stack.pop();
                    width += top[0];
                    ans = Math.max(ans, width * top[1]);
                }
                stack.push(new int[]{
        width + 1, height});     
    
            }
    
            return ans;
    
        }
    }

##### Go #####

func largestRectangleArea(heights []int) int {
        
        n := len(heights)
        stack := [][]int{
        }
        ans := 0
        for i := 0; i <= n; i++ {
        
            height := 0
            if i < n {
        
                height = heights[i]
            }
    
            if len(stack) == 0 {
        
                stack = append(stack, []int{
        1, height})
                continue
            }
    
            if height == stack[len(stack) - 1][1] {
        
                stack[len(stack) - 1][0] = stack[len(stack) - 1][0] + 1
                continue
            }
            if height > stack[len(stack) - 1][1] {
        
                stack = append(stack, []int{
        1, height})
                continue
            }
    
            width := 0
            for len(stack) > 0 && height < stack[len(stack) - 1][1] {
        
                top := stack[len(stack) - 1]
                stack = stack[:len(stack) - 1]
                width += top[0]
                ans = max(ans, width * top[1])
            }
            stack = append(stack, []int{
        width + 1, height})
        } 
        return ans
    }
    
    func max(a int, b int) int {
        
        if a > b {
        
            return a
        }
    
        return b
    }

#### 复杂度分析 ####

时间复杂度： O ( n ) O(n) O(n)，总体上说，每个柱子都是一次入栈，一次出栈，总共是执行了 `2n` 次，所以忽略常数后，时间复杂度为  O ( n ) O(n) O(n)。

空间复杂度： O ( n ) O(n) O(n)，栈在完全递增的情况下，最多可能会有 `n` 个数据，空间复杂度为 O ( n ) O(n) O(n)。

[106b7c6799f8d29d0944a05d8cfb7fd0.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/57e33e2bb9494b6eaef9f58e7530d760.png
[6106bd12ba09f66431310c5fcf15adbb.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9da9d6e7dad74a13b0971de48ef18526.png
[04c6b007c9ff4df342b696c71a348c04.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4ce3c55781d045ab89ae217e1f1aae13.png
[5f13987d21b77ed683474eb24e36eba0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3172605ff39647dcbdcabec8c4620463.png
[f62054583cf045a5089417a024a713f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/38b4cfbfc52147a6a25da05a6706e8c2.png