☆打卡算法☆LeetCode 84、柱状图中最大的矩形 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定n个非负整数，用来表示柱状图每个柱子的高度，求柱状图中最大的矩形的面积。”

题目链接：

来源：力扣（LeetCode）

链接：84. 柱状图中最大的矩形 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

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

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

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

二、解题

1、思路分析

这道题与42题【接雨水】类似，42题是求下雨之后能接多少雨水，这道题是求最大矩形，为什么总是把相似的题目拉出来讲呢，因为这类题都会有着相似的解题思路，可以复习之后再进行解答。

42题【接雨水】的解题方法主要有双指针、单调栈等，这道题也可以用单调栈来解题。

首先，来思考一下如何去求最大矩形，找到某一根柱子，将其固定为矩形的高度h，随后根据这根柱子向左右延伸，直到遇到高度小于h的柱子，这样就确定了矩形的左右边界，边界的宽度为w，面积为h * w。

但是在确定宽的时候要左右遍历，时间复杂度较高，所以这时候就可以使用单调栈去优化成一重遍历。

OK，首先说一下什么是单调栈，单调栈是一种很经典的数据结构，里面存放的数据都是有序的，可以分为单调递增站和单调递减栈，常用于解决最大区间、最大视野、最大矩形等。

以单调递增栈为例，如果新的元素比栈顶元素大，就入栈；如果比栈顶元素小，那么就将栈内元素弹出来，直到栈顶比新元素小。

这样的好处在于栈内的元素都是递增的，当元素出栈时，新元素是出栈元素后小的一个元素，这样就可以得到一个左右边界的高度，使用单调栈，在出栈操作时得到左右边界并计算面积。

2、代码实现

代码参考：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        
        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }

        mono_stack.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
            mono_stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
}

3、时间复杂度

时间复杂度 ： O(N)

空间复杂度： O(N)

三、总结

1、对于某一个柱子，高度确定，要求它的左右边界。

2、根据左右边界求出宽度，长乘宽就可以得到面积

3、根据单调栈，在出栈操作的时候得到坐标边界，求出最大面积