看摄影作品的网站,查看域名备案信息,中国建设招聘信息网站,实体门店管理系统https://oj.leetcode.com/problems/maximal-rectangle/ 一堆0,1矩阵中计算出由1组成的长方形的最大面积。 使用了直方图求最大面积的算法。枚举每一行p#xff0c;然后在将一行上的所有列看做朝ip方向出发的直方图#xff0c;然后在这个直方图上用栈存储递增序列的那个一…https://oj.leetcode.com/problems/maximal-rectangle/ 一堆0,1矩阵中计算出由1组成的长方形的最大面积。 使用了直方图求最大面积的算法。枚举每一行p然后在将一行上的所有列看做朝ip方向出发的直方图然后在这个直方图上用栈存储递增序列的那个一次遍历算法。最终求得最大值。 class Solution {
public:int n,m;vectorvectorchar a;vector int h;int MaxArea(int p){for (int i0;im;i){h[i]0;for (int jp;jn;j){if (a[j][i]0) break;h[i];}}vector int l(m);vector int r(m);stack int st;for (int i0;im;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 im-1;i0;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 res0;for (int i0;im;i){resmax(res,(r[i]-l[i]1)*h[i]);}return res;}int maximalRectangle(vectorvectorchar matrix) {nmatrix.size();amatrix;if (n0){return 0;}mmatrix[0].size();int res0;h.resize(m);for (int i0;in;i){resmax(res,MaxArea(i));}return res;}
};转载于:https://www.cnblogs.com/yangsc/p/4011917.html
