首页 > 代码库 > Leetcode#85 Maximal Rectangle
Leetcode#85 Maximal Rectangle
原题地址
指定任意一行作为矩形的下边界，那么问题就变成了求直方图的最大面积的矩形，参见之前的这篇文章。
所以思路就是，从上到下，依次求直方图最大面积矩形，感觉瞬间没有难度了。下面的代码里，第一个函数就是原封不动搬过来的。。
时间复杂度是O(n^2)
代码：
1 int largestRectangleArea(vector<int> &height) { 2 int maxArea = 0; 3 int n = height.size(); 4 stack<int> st; 5 int h, w; 6 7 for (int i = 0; i < n; i++) { 8 if (st.empty() || height[st.top()] < height[i]) 9 st.push(i);10 else {11 while (!st.empty() && height[st.top()] > height[i]) {12 h = height[st.top()];13 st.pop();14 w = st.empty() ? i : i - (st.top() + 1);15 maxArea = max(maxArea, h * w);16 }17 st.push(i);18 }19 }20 21 while (!st.empty()) {22 h = height[st.top()];23 st.pop();24 w = st.empty() ? n : n - (st.top() + 1);25 maxArea = max(maxArea, h * w);26 }27 28 return maxArea;29 }30 31 int maximalRectangle(vector<vector<char> > &matrix) {32 if (matrix.empty() || matrix[0].empty())33 return 0;34 35 int maxArea = 0;36 int h = matrix.size();37 int w = matrix[0].size();38 vector<int> histo(w, 0);39 40 for (int i = 0; i < h; i++) {41 // 计算直方图42 for (int j = 0; j < w; j++)43 histo[j] = (histo[j] + 1) * (matrix[i][j] - ‘0‘);44 45 maxArea = max(maxArea, largestRectangleArea(histo));46 }47 48 return maxArea;49 }
Leetcode#85 Maximal Rectangle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。