算法分析与设计►未分类

Miximal Rectangle

  • 问题来源
  • 问题简介

    给定一个矩阵，其中有 0 和 1 两种数据，要求输出包围最多个 1 的矩阵的面积

解题思路


遍历矩阵，若遇到 1，则


  1. 先从某个 1 处沿着横轴寻找最大的长度M

  2. 再从 M->1 依次缩小长度度，沿着纵轴寻找最大宽度


只要对每个1都进行相同操作，即可找到最大面积

时间复杂度 空间复杂度
O(未知) O(未知)

Code

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        size.second = matrix.size();
        if (size.second) {
            size.first = matrix[0].size();
        }
        else {
            size.first = 0;
        }
        int maximun = 0;
        for (int row = 0; row < size.second; row++) {
            for (int col = 0; col < size.first; col++) {
                if (matrix[row][col] == '0') {
                    continue;
                }
                int rw = getMaxWidth(matrix, col, row);
                int rh = 0;
                for (int k = rw - 1; k >= 0; k--) {
                    rh = rh + nextLine(matrix, col, col + k, rh + row);
                    maximun = max(maximun, (k + 1) * rh);
                }
            }
        }
        return maximun;
    }

    int getMaxWidth(vector<vector<char>>& matrix, int start_col, int start_row) {
        if (start_col >= size.first || start_row >= size.second) {
            return 0;
        }
        for (int col = start_col; col < size.first; col++) {
            if (matrix[start_row][col] == '0') {
                return col - start_col;
            }
        }
        return size.first - start_col;
    }

    int nextLine(vector<vector<char>>& matrix, int start_col, int end_col, int start_row) {
        if (start_row >= size.second) {
            return 0;
        }
        for (int i = start_col; i <= end_col; i++) {
            if (matrix[start_row][i] == '0') {
                return 0;
            }
        }
        return nextLine(matrix, start_col, end_col, start_row + 1)  + 1;
    }

private:
    pair<int, int> size;
};

int main() {
    vector<vector<char>> matrix;
    char data[][5] = {
        { '1', '0', '1', '0', '0' },
        { '1', '0', '1', '1', '1' },
        { '1', '1', '1', '1', '1' },
        { '1', '0', '0', '1', '0' },
    };
    for (int i = 0; i < 4; i++) {
        matrix.push_back(vector<char>(data[i], data[i] + 5));
    }
    cout << Solution().maximalRectangle(matrix) << endl;
    return 0;
}

运行结果

Miximal Rectangle

贴一下别人的代码

不是很懂


大概思路就是DP Solution问题。
DP：考虑且仅仅考虑由前一阶段状态转移到当前状态后，递推并选取出当前状态的最优解，具有无后效性和最优子结构的基本特征，其中所谓的无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结”。因此DP是由前一阶段的一系列阶段转移并选取最优而来，即抵达当前状态路径不唯一，仅是最终最优结果唯一。
class Solution {
public:
    int maximalRectangle(vector<vector<char> >& matrix) {
        if (matrix.empty()) return 0;
        int n = matrix[0].size(), m = matrix.size();
        int ret = 0;

        int left[n], right[n], height[n];
        fill(left, left+n, 0);
        fill(right, right+n, n);
        fill(height, height+n, 0);

        for (int i = 0; i < m; i++) {
            int cur_left = 0;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[j] = max(left[j], cur_left);
                } else {
                    left[j] = 0;
                    cur_left = j+1;
                }
            }

            int cur_right = n;
            for (int j = n-1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    right[j] = min(right[j], cur_right);
                } else {
                    right[j] = n;
                    cur_right = j;
                }
            }

            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    height[j] += 1;
                } else {
                    height[j] = 0;
                }
            }

            for (int j = 0; j < n; j++) {
                if ((right[j] - left[j]) * height[j] > ret)
                    ret = (right[j] - left[j]) * height[j];
            }
        }

        return ret;
    }
};