leetcode::maximal_rectangle::Solution类 参考

#include <leetcode.h>

静态 Public 成员函数
static int	maximalRectangle (vector< vector< char > > &matrix)

详细描述

在文件 leetcode.h 第 3102 行定义.

成员函数说明

maximalRectangle()

int leetcode::maximal_rectangle::Solution::maximalRectangle ( vector< vector< char > > &  matrix )

static

在文件 leetcode.cpp 第 8776 行定义.

                                                                   {
            const int m = matrix.size();
            if(m == 0) {
                return 0;
            }
            const int n = matrix[0].size();
            vector left(m, vector(n, 0));
 
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(matrix[i][j] == '1') {
                        left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                    }
                }
            }
 
            int ret = 0;
            for(int j = 0; j < n; j++) {
                // 对于每一列，使用基于柱状图的方法
                vector<int> up(m, 0), down(m, 0);
 
                stack<int> stk;
                for(int i = 0; i < m; i++) {
                    while(!stk.empty() && left[stk.top()][j] >= left[i][j]) {
                        stk.pop();
                    }
                    up[i] = stk.empty() ? -1 : stk.top();
                    stk.push(i);
                }
                stk = stack<int>();
                for(int i = m - 1; i >= 0; i--) {
                    while(!stk.empty() && left[stk.top()][j] >= left[i][j]) {
                        stk.pop();
                    }
                    down[i] = stk.empty() ? m : stk.top();
                    stk.push(i);
                }
 
                for(int i = 0; i < m; i++) {
                    const int height = down[i] - up[i] - 1;
                    int area         = height * left[i][j];
                    ret              = max(ret, area);
                }
            }
            return ret;
        }

引用了 acwing::acwing1929::down, acwing::acwing1929::left , 以及 acwing::acwing1929::up.

被这些函数引用 leetcode::maximal_rectangle::TEST().

---

该类的文档由以下文件生成:

• leetcode.h
• leetcode.cpp