这是一道 困难 的题。

题目来自：https://leetcode.cn/problems/largest-rectangle-in-histogram/

题目


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

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

提示：


示例1:

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


示例2:


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



暴力解法

01

解题思路



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

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

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

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


02

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;

    }
}



03

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
}


04

复杂度分析



时间复杂度：，外层循环 n 次，内层循环每次最多 n 次。
空间复杂度：。


单调栈

01

解题思路



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

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

那么，每个柱子的左右边界就都是确定的：左边界就是自己的编号 `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;

   }
}

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

如下图所示：

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


上面的思路总结起来其实就是：
1. 当遇到更高的柱子就加入。

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


看到 后进先出，自然而然就想到用 栈 来实现上面思路了。栈中存放的元素是一个数组，数组中存放柱子的宽度和高度。


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

02

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;

    }
}



03

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
}


04

复杂度分析



时间复杂度：，总体上说，每个柱子都是一次入栈，一次出栈，总共是执行了 2n 次，所以忽略常数后，时间复杂度为 。
空间复杂度：，栈在完全递增的情况下，最多可能会有 n 个数据。



END



点个在看你最好看

本篇文章来源于微信公众号: i余数



微信扫描下方的二维码阅读本文

此作者没有提供个人介绍
最后更新于 2023-06-19
啥也没有呀