网站成立时间查询,哪个网站有适合小学生做的题,洛阳鼎和电力建设有限公司网站,做网站怎样建立服务器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
