恩,那个blog的解法是基于histogram那道题的。但是large judge会报time limit exceeded.我自己写了一遍也过不了large judge。能帮忙看看是哪里的时间复杂度太高 呢? public class Solution { public int maximalRectangle(char[][] matrix) {
Stack st = new Stack(); int max = 0; int r = 0; int n = height.length;
while(r < n){
if(st.isEmpty()){ st.push(r); r++; continue; }
int l = st.peek();// the potential left border.
if(height[l] > height[r]){
while(!st.isEmpty() && height[l] > height[r]){
int curr = st.pop(); l = st.isEmpty()?-1:st.peek(); max = Math.max(max, height[curr] * (r-l-1));
} } else if(height[l] == height[r]) { st.pop(); } st.push(r); r++; } while(!st.isEmpty()){ int curr = st.pop(); int l = st.isEmpty()?-1:st.peek(); max = Math.max(max, height[curr] * (n-l-1)); }
return max; } }
【在 h****n 的大作中提到】 : large rectangle in histogram的变形,那个会N解法的话,自然这个就是N square解 : 法
c*n
11 楼
that should be fine. Your title and insurance won't be done till days before closing. Most agents know this is fine.
l*o
12 楼
能看出来现在市场不景气,宣传费用被削减到这个程度了
c*s
13 楼
int maximalRectangle(vector > &matrix) { // Start typing your C/C++ solution below // DO NOT write int main() function int m = matrix.size(); if (m == 0) { return 0; } int n = matrix[0].size(); vector height; height.resize(n,0); stack > st; int i, j ,answer = 0; for (i = 0; i < m; ++i) { for (j = 0; j < n; ++j) { if (matrix[i][j] == '1') { ++height[j]; } else { height[j] = 0; } while (!st.empty() && height[st.top().first] > height[j]) { answer = max(answer, height[st.top().first] * (j - st.top(). second)); st.pop(); } st.push(make_pair(j,st.empty()?(0):(st.top().first + 1)));