首页 > 代码库 > leetcode 最大矩形和

leetcode 最大矩形和

1.枚举法(超时)

 1 public class Solution { 2     public int largestRectangleArea(int[] height) { 3         int max=-1; 4         for(int i=0;i<height.length;i++) 5         { 6             int len=1; 7             int k=i-1; 8             while(k>=0&&height[k]<=height[i]) 9             {10                 k--;11                 len++;12             }13             k=i+1;14             while(k<height.length&&height[k]<=height[i])  15             {16                 len++;17                 k++;18                 19                 20                 21             }22             if(max<len)23             {24                 max=len;25             }26             27             28                 29             }30             return max;31         32             33             34             35        36         37     }38 }
View Code

2.单调栈(AC),其实模拟了第一种方法,nyoj做过,效率为线性。写的代码有点长,但是很好理解

 1 class node 2 { 3     int d; //di  4     int h;// higtht 5 } 6      7  8  9 public class Solution {10     public int largestRectangleArea(int[] height) {11         int len=height.length;12         if(len==0) return 0;13         node n[]=new node[len];14         for(int i=0;i<len;i++)15         {16             n[i]=new node();17             n[i].d=1;18             n[i].h=height[i];19             20         }21         Stack<node> s=new Stack<node>();22         s.push(n[0]);23         int max=n[0].h;24         for(int j=1;j<len;j++)25         {26             node t=s.peek();27             if(n[j].h>=t.h)28             {29                 s.push(n[j]);30             }31             else32             {33                 int with=0;34                 while(!s.isEmpty()&&s.peek().h>n[j].h)35                 {  36                    t=s.pop();37                     with+=t.d;38                     if(with*t.h>max) max=with*t.h;39                     40                 }41                 n[j].d+=with;42                 s.push(n[j]);43                     44              }45             46                 47                 48         }49         int with=0;50         while(!s.isEmpty())51         {52             node t=s.pop();53             with=with+t.d;54             int temp=t.h*with;55             56             if(temp>max) max=temp;57              58         }59             60 return max;61     }}
View Code

3.最大01矩阵()。使用上述四项,枚举每一行。

 1 class node 2 { 3     int d; //di  4     int h;// higtht 5 } 6      7 public class Solution { 8     public int largest(int[] height) { 9         int len=height.length;10         if(len==0) return 0;11         node n[]=new node[len];12         for(int i=0;i<len;i++)13         {14             n[i]=new node();15             n[i].d=1;16             n[i].h=height[i];17             18         }19         Stack<node> s=new Stack<node>();20         s.push(n[0]);21         int max=n[0].h;22         for(int j=1;j<len;j++)23         {24             node t=s.peek();25             if(n[j].h>=t.h)26             {27                 s.push(n[j]);28             }29             else30             {31                 int with=0;32                 while(!s.isEmpty()&&s.peek().h>n[j].h)33                 {  34                    t=s.pop();35                     with+=t.d;36                     if(with*t.h>max) max=with*t.h;37                     38                 }39                 n[j].d+=with;40                 s.push(n[j]);41                     42              }43             44                 45                 46         }47         int with=0;48         while(!s.isEmpty())49         {50             node t=s.pop();51             with=with+t.d;52             int temp=t.h*with;53             54             if(temp>max) max=temp;55              56         }57             58 return max;59     }60     public int maximalRectangle(char[][] matrix) {61         if(matrix.length==0) return 0;62         63        int len=matrix[0].length;64        int ans[]=new int[len];65        for(int i=0;i<len;i++)66        {67            ans[i]=matrix[0][i]-‘0‘;68        }69        int max=largest(ans);70         71         for(int i=1;i<matrix.length;i++)72         {73            for(int j=0;j<matrix[0].length;j++)74            {75                if(matrix[i][j]==‘0‘) ans[j]=0;76                77                else 78                {79                    ans[j]+=1;80                }81               82               83                84            }85           86           int t=largest(ans);87           if(max<t) max=t;88             89             90         }91         92         93         94         95         return max;96         97     }98 }
View Code

https://oj.leetcode.com/problems/maximal-rectangle/