[LeetCode]*85.Maximal Rectangle

[LeetCode]*85.Maximal Rectangle

題目

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

思路

對於上圖的一個01矩陣。我們可以一行一行的分析，假設第三行，我們按列掃描，遇到0時，柱子斷開，重新形成柱子，遇到1時柱子高度加一。這樣的話，我們就可以把問題轉換為[LeetCode]*84.Largest Rectangle in Histogram求解最大矩形面積。

代碼<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> /*--------------------------------------- * 日期：2015-05-14 * 作者：SJF0115 * 題目: 85.Maximal Rectangle * 網址：https://leetcode.com/problems/maximal-rectangle/ * 結果：AC * 來源：LeetCode * 博客： -----------------------------------------*/ #include #include #include using namespace std; class Solution { public: int maximalRectangle(vector>& matrix) { int row = matrix.size(); if(row == 0){ return 0; }//if int col = matrix[0].size(); vector > height(row,vector(col,0)); // 計算每一行的高度 int h; for(int j = 0;j < col;++j){ h = 0; for(int i = 0;i < row;++i){ if(matrix[i][j] == '1'){ ++h; }//if else{ h = 0; }//else height[i][j] = h; }//for }//for /*for(int i = 0;i < row;++i){ for(int j = 0;j < col;++j){ cout<

運行時間