https://oj.leetcode.com/problems/maximal-rectangle/

一堆0,1矩陣中計算出由1組成的長方形的最大面積。

使用了直方圖求最大面積的算法。枚舉每一行p，然后在將一行上的所有列看做朝i>p方向出發的直方圖，然后在這個直方圖上用棧存儲遞增序列的那個一次遍歷算法。最終求得最大值。

class Solution { public:int n,m;vector<vector<char> > a;vector <int> h;int MaxArea(int p){for (int i=0;i<m;i++){h[i]=0;for (int j=p;j<n;j++){if (a[j][i]=='0') break;h[i]++;}}vector <int> l(m);vector <int> r(m);stack <int> st;for (int i=0;i<m;i++){if (st.empty()){l[i]=i;st.push(i);continue;}if (h[i]>h[st.top()]){l[i]=i;st.push(i);continue;}while(!st.empty()){if (h[i]>h[st.top()]) break;l[i]=l[st.top()];st.pop();}st.push(i);}while(!st.empty()) st.pop();for (int i=m-1;i>=0;i--){if (st.empty()){r[i]=i;st.push(i);continue;}if (h[i]>h[st.top()]){r[i]=i;st.push(i);continue;}while(!st.empty()){if (h[i]>h[st.top()]) break;r[i]=r[st.top()];st.pop();}st.push(i);}int res=0;for (int i=0;i<m;i++){res=max(res,(r[i]-l[i]+1)*h[i]);}return res;}int maximalRectangle(vector<vector<char> > &matrix) {n=matrix.size();a=matrix;if (n==0){return 0;}m=matrix[0].size();int res=0;h.resize(m);for (int i=0;i<n;i++){res=max(res,MaxArea(i));}return res;} };

　　

轉載于:https://www.cnblogs.com/yangsc/p/4011917.html

總結

以上是生活随笔為你收集整理的LeetCode-Maximal Rectangle-最大矩形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。