本文主要是介绍LeetCode - 85. 最大矩形，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = []
输出：0
示例 3：
输入：matrix = [["0"]]
输出：0
示例 4：
输入：matrix = [["1"]]
输出：1
示例 5：
输入：matrix = [["0","0"]]
输出：0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-rectangle/
求解
class Solution {private:// 对每一行，根据高度计算当前行节点组成矩形的最大面积int largestRectangleArea(vector<int> &heights) {if (heights.empty()) {return 0;}vector<int> h(heights.size() + 2, 0);// h为heights收尾各加上一个0，即[0, heights[0], heights[1], ..., heights[n-1], 0]std::copy(heights.cbegin(), heights.cend(), h.begin() + 1);const int N = h.size();int res = 0;vector<int> rec;for (int i = 0; i < N; ++i) {while (!rec.empty() && h[rec.back()] > h[i]) {int cur = rec.back();rec.pop_back();int left = rec.back() + 1;int right = i - 1;res = std::max(res, (right - left + 1) * h[cur]);}rec.push_back(i);}return res;}public:// 暴力解法，计算每一行为基准，每个点往上有多少个连续的1组成（即柱状高度），每行这些柱状中的最大矩形面积（84题）// 最后取每行中的最大值即为整个二维数组中最大矩阵的面积int maximalRectangle(vector<vector<char>> &matrix) {if (matrix.empty() || matrix[0].empty()) {return 0;}const int m = matrix.size();const int n = matrix[0].size();// heights记录每个节点往上连续多个个1，即高度vector<vector<int>> heights(m, vector<int>(n, 0));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (matrix[i][j] == '1') {heights[i][j] = 1;if (i > 0) {heights[i][j] += heights[i - 1][j];}}}}// 计算面积int res = 0;for (auto &vec : heights) {// 逐行计算其最大面积res = std::max(res, largestRectangleArea(vec));}return res;}};
这篇关于LeetCode - 85. 最大矩形的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
