84 最大矩形

题目详情

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

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

结题分析

柱子彼此相邻，宽度都为1，高度各不相同。对于当前考察的柱子来说，它所能勾勒出的矩形面积是由其左边柱子和右边柱子的高度共同决定的。

如果其左边柱子的高度大于等于当前柱子的高度，则可以向左侧扩张，直到左边柱子高度小于当前柱子高度或左边再无其它柱子；同样的，如果其右边柱子的高度大于等于当前柱子的高度，则可以向右侧扩张，直到右边柱子高度小于等于当前柱子高度或右边再无其它柱子。

这时，就可以计算出以当前柱子高度为高，左右柱子间距离为宽的矩形面积。如果还是不懂，看下面这个图就知道了

85最大矩形

题目详情

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

题目分析

该题和上面的题有点相似，但又不完全一样，但是可以转变成上面一题的类似结构。

以每行的数据作为底，然后构建类似第一题中的矩形。构建该矩形油俩个特点：

1. 若底为0时，则高度就为0，不管其上面有多少个1。
2. 若底为1时，则向上继续查找，连续1的数就是该底的高度，只要有0出现，则该底的高度计算终止。

矩形图

第1行数据为底时，构建的矩形图如下：

第2行数据为底时，构建的矩形图如下：

第3行数据为底时，构建的矩形图如下：

第4行数据为底时，构建的矩形图如下：可以发现，底为0时高度就是0

通过上面对每行数据矩形的构建，已经和第一题完全一样了，可以使用单调栈的方式对每行的矩形进行判断，取出最大矩形即可。

211最大正方形

问题描述

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

问题分析

这道题和第二道题如出一辙，唯一的区别就是这道题查询的是最大正方形,而第二题查询的是最大长方形。

我们仍然使用第二道题的思路，以每行数据为底构建矩形。而此题需要的求的是最大正方形，那么怎么将矩形转换为正方形呢？举几组数据

• 宽为1，高为3，最大正方形为1^2
• 宽为3 ，高为2，最大正方形为2^2
• 宽为4，高为4，最大正方形为4^2

可以发现正方形的面积其实就是min(宽,高)^2,得出该结论其实该问题就已经解决了。