最大矩形面积问题——单调堆栈法文章目录最大矩形面积问题——单调堆栈法直方图最大矩形面积分析单调堆栈法过程示例代码示例矩阵中最大矩形分析代码示例
直方图最大矩形面积
主题地址
如果指定非负整数数组heights，则数组中的数字用于表示条形图中每个柱的高度。 各柱相互邻接，宽度为1。
在这个条形图中，求出可以描绘的矩形的最大面积。
示例1
输入： heights=[2、1、5、6、2、3]输出： 10解释：最大矩形为图中红色区域，面积为10 示例2
输入： heights=[ 2，4 ]输出： 4分析矩形的面积为宽x高，因此只要确定了各自举办的宽度和高度，就可以计算出其面积。
宽度可以通过减去排列下标得到，关于高度，只要寻找对应范围的排列中的最小值就可以得到面积
这个题型有暴力解读、分割统治法、单调堆栈法三种解法。
暴力破解:即，在方便所有矩形的同时，只要保持一个表示最大面积的变量即可3358www.Sina.com/:从实施例1可知，直方图的最大矩形有以下三种可能性1、矩形通过最低的柱子，宽度最大。 2、开始的柱子和结束的柱子总是在最低的柱子的左侧。 3、开始的柱子和结束的柱子总是在最低的柱子的右侧。 于是，可以考虑找到最低的柱子，分别计算这三种状态。 其中，23个本质上情况相同。 也就是说，将一个区域左右分为两次，求出最大矩形。 这样，两个相同的子问题，就可以递归求解了。分治法:见下一节。 单调堆栈法单调堆栈法是指在单调堆栈中找到某根柱左右两侧第一个比第一个小的柱下标，通过计算该柱位于最短边时最大矩阵的大小，找出所有柱后，覆盖所有最小的可能性。 产生此效果的堆栈称为单调堆栈，堆栈内保持单调递增，确保与堆栈顶部对应的柱左侧第一个比其他小的柱一定是其下一个元素。 这样，在与比堆栈顶小的第一根柱碰撞时，可以得到堆栈顶柱为最小边时的最大矩形区域，从而得到其他的面积。 这种想法其实和失去分割统治法相似。 也就是说，寻找所有以当前柱为最短边的最大矩形，分割统治是指一个接一个地划分边界，重复情况1计算最大矩形。 然后，只要维持最大的值就能得到全局最大的矩形。 过程示例注：下图来自康马斯星球
可以看到，在最终堆栈中，除了为了便于处理而添加的初始化的-1以外，还存在1、4、5这3个要素，还没有计算出以1、2、3列的高度为顶的最大矩阵。 此时，进一步想想，他们之所以没有被计算在内，是因为还没有出现比他们矮的柱子。 最后添加0高柱的高度时，假设除-1之外的所有元素都来自堆栈，将计算所有柱，计算完成，如下所示
代码示例中的代码注意面积计算部分，在数组的两侧分别插入一个小于全局最小值的数字，以统一边界情况。 高度为heights[tmp]，宽度为(i - s.top ) (- 1 )。 不包含I和s.top ()两个柱的中间区域是宽的class solution (公共：交互式矢量) vectorintheights )//单调增加非减少堆栈int heights.insert(heights.begin )，0 )； heights.push_back(0； int len=heights.size (； int maxArea=heights[0]； s.push(0； for(intI=1； i len； I () while ) heights[I]heights[s.top ) { int tmp=s.top； s.pop (； Maxarea=max(Maxarea，heights[tmp]*(I-s.top(-1 ) )； (s.push ) I； }返回矩阵； }； 矩阵中最大矩形的标题地址
给出由0和1组成的矩阵matrix，找到只包含1的最大矩形，并返回其面积。
*注意： **此问题的矩阵输入格式为一维01字符串数组。
单调栈法
输入： matrix=['10100 '、' 10111 '、' 11111 '、' 10010']输出： 6解释：最大矩形如上图所示。示例 1：
： 输入：matrix = []输出：0示例 3：
输入：matrix = ["0"]输出：0示例 4：
输入：matrix = ["1"]输出：1示例 5：
输入：matrix = ["00"]输出：0提示：
rows == matrix.lengthcols == matrix[0].length0 <= row, cols <= 200matrix[i][j] 为 '0' 或 '1' 分析 乍一看本题和直方图最大矩形面积似乎没有什么关系，但是换个角度看（逐行遍历，然后画坐标轴，就可以得到类似直方图样子，于是就可以转换成上一题的解法）： 注：下面的图是来自cdx 代码示例 于是可以嵌套上一题的解法。主体函数maximalRectangle来将问题转化为直方图中的最大矩形问题，利用上题largestRectangleArea函数求解。这里在申请的时候直接一次性申请多两个空间，用以避免数组插入多情况出现。 class Solution{public: int maximalRectangle(vector<string> &matrix) { //利用行的迭代，来转化为直方图中的最大矩形问题 int maxArea = 0; int row = matrix.size(); if (row == 0) return 0; int col = matrix[0].size(); vector<int> heights(col + 2, 0); for (int i = 0; i < row; i++) { for (int j = 1; j < col + 1; j++) { if (matrix[i][j - 1] == '0') heights[j] = 0; else heights[j] += 1; } maxArea = max(maxArea, largestRectangleArea(heights)); } return maxArea; } int largestRectangleArea(vector<int> &heights) { // 单调递非减栈 stack<int> s; // heights.insert(heights.begin(), 0); // heights.push_back(0); int len = heights.size(); int maxArea = heights[0]; s.push(0); for (int i = 1; i < len; i++) { while (heights[i] < heights[s.top()]) { int tmp = s.top(); s.pop(); maxArea = max(maxArea, heights[tmp] * (i - s.top() - 1)); } s.push(i); } return maxArea; }};