首页 > 代码库 > 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 }
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 }}
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 }
https://oj.leetcode.com/problems/maximal-rectangle/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。