[LeetCode] 85、最大矩形

题目描述

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

示例：

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
输出: 6

解题思路

这一题的算法本质上和84题Largest Rectangle in Histogram一样，对每一列都求出每个元素对应的高度，这个高度就是对应的连续1的长度，然后对每一行都更新一次最大矩形面积。那么这个问题就变成了Largest Rectangle in Histogram。本质上是对矩阵中的每行，均依次执行84题算法。

代码核心：（能理解思路最重要，参考）

for(int i = 0; i < rows; i++){
    for(int j = 0; j < cols; j++){
        heights[j] = matrix[i][j] == '1'? heights[j]+1: 0;  // 关键
    }
    res = max(res, leetcode48(heights));
}

思路：

• 遍历每一行的高度

• 用84题求最大矩形的方法直接套过来求解即可

• 图解

  

其实上述更新每一行高度的思路有点dp的味道：从上层得到下一层能建立的柱体的最大高度，然后在每一层借用单调栈求出以该组柱体为高的最大矩形面积。时间复杂度$O(MN)$O(MN)，空间复杂度$O(N)$O(N)。

参考代码

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        if(rows == 0)
            return 0;
        int cols = matrix[0].size();
        
        int res = 0;
        vector<int> heights(cols, 0);
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                heights[j] = matrix[i][j] == '1'? heights[j]+1: 0;
            }
            
            res = max(res, largestRectangleArea(heights));
        }
        
        return res;
    }
    
    // leetcode84
	int largestRectangleArea(vector<int> heights) {
		if (heights.size() == 0)
			return 0;
        
		int maxArea = 0;
		stack<int> indexStack;  // 单调递增（不减）栈
		heights.insert(heights.begin(), 0);  // 在heights的前后各补一个0，方便计算。
		heights.push_back(0);
		for (int i = 0; i < heights.size(); i++) {
			while (!indexStack.empty() && heights[i] < heights[indexStack.top()]) {  // 这里是&&
				int curIndex = indexStack.top();
				indexStack.pop();
				int curArea = (i - indexStack.top() - 1) * heights[curIndex];
				maxArea = max(maxArea, curArea);
			}

			indexStack.push(i);
		}

		return maxArea;
	}
	
};