## LeetCode的C++ 11/Python3 题解及解释

4 月 13 日 专知

【导读】本仓库包含LeetCode前710题的C++11和Python3 的题解与解释。

Github地址：

https://github.com/pezy/LeetCode

084 题 最大的矩阵

#include <vector>using std::vector;#include <stack>using std::stack;#include <algorithm>using std::max; using std::min;
class Solution {public: int largestRectangleArea(vector<int> &height) { int max_area = 0, i = 0, size = height.size(); for (stack<int> stk; i<size || !stk.empty(); ) if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i++); else { int tp = stk.top(); stk.pop();                max_area = max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1)); } return max_area; } int maximalRectangle(vector<vector<char> > &matrix) { if (matrix.empty()) return 0; int max_area = 0; vector<int> height(matrix[0].size(), 0); for (size_t i=0; i<matrix.size(); ++i) { for (size_t j=0; j<matrix[0].size(); ++j) if (matrix[i][j] == '0') height[j] = 0; else ++height[j]; max_area = max(max_area, largestRectangleArea(height)); } return max_area; }};
#define CATCH_CONFIG_MAIN#include "../Catch/single_include/catch.hpp"#include "solution.h"
TEST_CASE("Maximal Rectangle", "[maximalRectangle]"){ Solution s; SECTION( "common1" ) { std::vector<std::vector<char>> matrix = {{'0', '1', '0', '0'}, {'1', '1', '1', '0'}, {'0', '1', '1', '0'}, {'0', '0', '1', '0'}, {'0', '1', '0', '0'}}; REQUIRE( s.maximalRectangle(matrix) == 4 ); } SECTION( "common2" ) { std::vector<std::vector<char>> matrix = {{'1', '1', '1', '1'}, {'1', '0', '0', '1'}, {'1', '1', '1', '1'}, {'0', '0', '1', '0'}, {'0', '1', '1', '1'}}; REQUIRE( s.maximalRectangle(matrix) == 4 ); } SECTION( "common3" ) { std::vector<std::vector<char>> matrix = {{'1', '1', '1', '1', '1'}, {'1', '1', '1', '0', '1'}, {'1', '1', '1', '0', '0'}, {'1', '0', '0', '0', '0'}, {'1', '0', '0', '0', '0'}}; REQUIRE( s.maximalRectangle(matrix) == 9 ); } SECTION( "common4" ) { std::vector<std::vector<char>> matrix = {{'0', '1', '0', '1', '0'}, {'1', '1', '1', '1', '1'}, {'0', '1', '1', '1', '0'}, {'0', '1', '1', '1', '0'}, {'1', '1', '1', '1', '1'}, {'1', '1', '1', '1', '0'}, {'0', '1', '0', '1', '0'}, {'0', '0', '0', '0', '0'}}; REQUIRE( s.maximalRectangle(matrix) == 15 ); }

-END-

Top