我是做装修的怎么样投资网站,网站建设意义和目的,小型app开发公司,室内设计接单的网站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
