Leetcode：84. Largest Rectangle in Histogram（面积最大的长方形）

ゝ一世哀愁。 2022-04-02 07:54 151阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。
> 
> 这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述:

解题思路：

java实现方法1:

python实现方式1：

java实现方法2:

python实现方法2:

源码地址：

--------------------

### **题目描述:** ###

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

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

![format_png][]

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 \[2,1,5,6,2,3\]。

![format_png 1][]

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
    输出: 10

来源：力扣（LeetCode）

--------------------

### 解题思路： ###

对于这个题目，我首先想到的是动态规划，但是通过一番思考发现动态规划并不好做，直接利用循环和栈就能解决该问题，下面是思路：

1. 定义一个栈，利用它先进后出的思想，存储下标的位置

2.然后循环遍历数组，最后得到数组的最大面积

--------------------

### java实现方法1: ###

/**
         * 计算数组最大面积
         *
         * @param heights 高度数组
         * @return 面积
         */
        public int largestRectangleHistogram(int[] heights) {
            if (heights == null || heights.length < 1) {
                return 0;
            }
            Deque<Integer> stack = new LinkedList<>();
            int maxArea = 0;
            int index = 0;
            // 当下标小于数组的长度,保存所有元素都进入栈中
            while (index <= heights.length) {
                if (stack.isEmpty() || (index < heights.length && heights[index] >= heights[stack.peek()])) {
                    stack.push(index);
                    index++;
                } else {
                    int oldIndex = stack.pop();
                    // 当所有元素都出栈时候，宽度就为index
                    int width = stack.isEmpty() ? index : index - stack.peek() - 1;
                    // 获取面积最大（宽度*高度）
                    maxArea = Math.max(maxArea, width * heights[oldIndex]);
                }
            }
            return maxArea;
        }

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### python实现方式1： ###

from typing import List
    
    
    def largest_rectangle_histogram(heights: List[int]) -> int:
        '''
            计算最大矩形长度
        Args:
            heights: 数组长度
        Returns:
            矩形最大面积
        '''
        if heights == None or len(heights) < 1:
            return 0
        stack = []
        max_area = 0
        index = 0
        while index < len(heights):
            if len(stack) < 1 or (index < len(heights) and heights[index] >= heights[stack[-1]]):
                stack.append(index)
                index += 1
            else:
                top = stack.pop()
                width = index if len(stack) < 1 else index - stack[-1] - 1
                max_area = max(max_area, width * heights[top])
        return max_area

时间复杂度：O(n)

空间复杂度：O(n)

--------------------

### java实现方法2: ###

/**
         * 计算数组最大面积（brute force）
         *
         * @param heights 高度数组
         * @return 面积
         */
        public int largestRectangleHistogram2(int[] heights) {
            int area = 0, n = heights.length;
            // 遍历每个柱子，以当前柱子的高度作为矩形的高 h，
            // 从当前柱子向左右遍历，找到矩形的宽度 w。
            for (int i = 0; i < n; i++) {
                int w = 1, h = heights[i], j = i;
                while (--j >= 0 && heights[j] >= h) {
                    w++;
                }
                j = i;
                while (++j < n && heights[j] >= h) {
                    w++;
                }
                area = Math.max(area, w * h);
            }
            return area;
        }

时间复杂度：O(n^2)

空间复杂度：O(1)

--------------------

### python实现方法2: ###

def largest_rectangle_histogram2(heights: List[int]) -> int:
        '''
            计算最大矩形长度
        Args:
            heights: 数组长度
        Returns:
            矩形最大面积
        '''
        if not heights:
            return 0
        if len(heights) < 2:
            return heights[0]
        area_max = 0
        for i in range(len(heights)):
            height = heights[i]
            width = 1  # 当前宽度为1
            k = i - 1
            while k >= 0 and heights[k] >= height:
                width += 1
                k -= 1
            k = i + 1
            while k <= len(heights) - 1 and heights[k] >= height:
                width += 1
                k += 1
            area_max = max(area_max, height * width)
        return area_max

时间复杂度：O(n^2)

空间复杂度：O(1)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[format_png]: /images/20220402/041c550e83094d6fb58062af58f46577.png
[format_png 1]: /images/20220402/4d2c4e7f8e3d4f118388525e558fc43c.png
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode