咱们继续，再来个最大矩形。

-> leetcode 最大矩形

不同于 柱状图的最大矩形，这次计算的是一个矩阵，而矩阵是由一行一行数据组成的，就意味着其是多个相同个数的柱状图组成的，以案例为例：

## 矩阵
[0] 1 0 1 0 0
[1] 1 0 1 1 1
[2] 1 1 1 1 1
[3] 1 0 0 1 0

## [0]
1 0 1 0 0
对应柱形
1 0 1 0 0

## [1]
1 0 1 1 1
对应柱形
2 0 2 0 0
1 0 1 1 1

## [2]
1 1 1 1 1
对应柱形
3 0 3 0 0
2 0 2 2 2
1 1 1 1 1

## [3]
1 0 0 1 0
对应柱形
4 0    
3 0   3 
2     2 
1 0 0 1 0

则我们可以遍历矩阵的每一行，计算其对应的矩形，剩下的交给求柱形的最大矩形函数中计算。

因此我们需要解决问题只有如何去计算矩阵单行对应的矩形，而上面的方式我们已经说明了如何去计算：

  1. 记录[0]的对应数据，第一个柱状图实现；
  2. 接下来到[1]，使用第一个柱状图，如果本行为0则无柱状图出现，如果本行为1则可以对应之前的高度+1；
  3. 后续均如此

依照这个规则我们写成代码：

    // 柱状图的柱形个数
    auto size = matrix[0].size();

    // 存储矩形 并初始化
    vector<int> heights(size, 0);
    // 结果
    int res{0};

    // 遍历一层矩形
    for (const auto &row : matrix) {
        // 遍历第二层矩形
        for (size_t i{0}; i<size; ++i) {
            // 获取矩形的高度

            // 当前的指向 数字
            int cur = row[i] - '0';

            switch (cur) {
            case 0:
                heights[i] = 0;
                break;
            case 1:
                heights[i] += 1;
                break;
            default:
                break;
            }
        }

        // 获取完成
        // 其他操作
    }

每一次第二层循环都会确定一层的柱状图，根据这个柱状图可以使用之前的思路实现最大面积计算，回忆一下前面的代码，柱状图的最大矩形：

int maxArea(vector<int>& heights) {
    // 获取柱形个数
    auto size = heights.size();

    // 存储边界
    stack<int> stk;

    // 结果
    int res{0};

    for (size_t i{0}; i<size; ++i) {
        int cur = heights[i];
        // 若栈中无元素
        if (stk.empty()) {
            stk.push(i);
            continue;
        }

        int top_i = stk.top(); // 栈顶索引
        int top = heights[top_i]; // 栈顶对应元素

        // 触发计算边界
        while (!stk.empty() && cur < top) {
            // 弹出栈顶
            stk.pop();
            int left = stk.empty() ? 0 : stk.top() + 1;
            int right = i-1;

            int width = right-left+1;

            // 计算面积
            int area = width*top;

            // 获取最大
            res = max(res, area);

            // 下一个条件
            top_i = stk.empty() ? 0 : stk.top();
            top = heights[top_i];
        }

        // 完成计算
        stk.push(i);
    }

    // 栈不空
    while(!stk.empty()) {
        int top_i = stk.top();
        stk.pop();
        int top = heights[top_i];

        int left = stk.empty() ? 0 : stk.top() + 1;
        int right = size-1;
        int width = right - left + 1;

        int area = width*top;

        res = max(res, area);
    }

    // 计算完了

    return res;
}

完成这个函数之后，就可以写入整体代码了：

class Solution {
public:
    int maxArea(vector<int>& heights) {
        // 获取柱形个数
        auto size = heights.size();

        // 存储边界
        stack<int> stk;

        // 结果
        int res{0};

        for (size_t i{0}; i<size; ++i) {
            int cur = heights[i];
            // 若栈中无元素
            if (stk.empty()) {
                stk.push(i);
                continue;
            }

            int top_i = stk.top(); // 栈顶索引
            int top = heights[top_i]; // 栈顶对应元素

            // 触发计算边界
            while (!stk.empty() && cur < top) {
                // 弹出栈顶
                stk.pop();
                int left = stk.empty() ? 0 : stk.top() + 1;
                int right = i-1;

                int width = right-left+1;

                // 计算面积
                int area = width*top;

                // 获取最大
                res = max(res, area);

                // 下一个条件
                top_i = stk.empty() ? 0 : stk.top();
                top = heights[top_i];
            }

            // 完成计算
            stk.push(i);
        }

        // 栈不空
        while(!stk.empty()) {
            int top_i = stk.top();
            stk.pop();
            int top = heights[top_i];

            int left = stk.empty() ? 0 : stk.top() + 1;
            int right = size-1;
            int width = right - left + 1;

            int area = width*top;

            res = max(res, area);
        }

        // 计算完了

        return res;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        if (0 == matrix.size()) {
            return 0;
        }
        // 柱状图的柱形个数
        auto size = matrix[0].size();

        // 存储矩形 并初始化
        vector<int> heights(size, 0);
        // 结果
        int res{0};

        // 遍历一层矩形
        for (const auto &row : matrix) {
            // 遍历第二层矩形
            for (size_t i{0}; i<size; ++i) {
                // 获取矩形的高度

                // 当前的指向 数字
                int cur = row[i] - '0';

                switch (cur) {
                case 0:
                    heights[i] = 0;
                    break;
                case 1:
                    heights[i] += 1;
                    break;
                default:
                    break;
                }
            }

            // 获取完成
            // 其他操作
            res = max(res, maxArea(heights));
        }

        return res;
    }
};
执行用时：52 ms, 在所有 C++ 提交中击败了94.39% 的用户
内存消耗：12.1 MB, 在所有 C++ 提交中击败了44.37% 的用户

还行，时间复杂度为O(M*N)，即取决于矩阵的大小。不过有其他方法吗？

不过这已经是比较简便的思路了，无论如何做，都需要将矩阵遍历一遍，因此时间复杂度无法再降低了。

可以尝试将柱状图的方法融合进代码，实现代码的精简，在一些细节上可以降低些运行时间，但具体就不做了。

（还有动态规划，但本处确保使用栈）

如有错误，欢迎指正！

如有不懂，欢迎讨论！

感谢🙏🏻️观看！