当前位置：首页 > news >正文

关于二维数组求解面积的问题

news 来源：原创 2024/5/19 1:00:05

2019独角兽企业重金招聘Python工程师标准>>>

一、刷的一道题

二维数组用0,1（0=空的，1=面积存在）填充，那么要求解一个最大的面积

0 0 0 0 0     0 0 0 0 0
1 1 0 1 1 =》 1 1 0 1 1
0 1 1 1 1     0 2 1 2 2 
1 1 1 1 1     1 3 2 3 3

这道题按照网上的做法就是上图的改变转换为列的图形

然后在每次计算可能的一个最大面积

保留一个最大的面积

下面是代码

public int maximalRectangle(char[][] matrix) {
			int m=matrix.length;
			if(m==0)return 0;
			
			int n=matrix[0].length;
			int area=matrix[0][0]-'0';
			
			//建立一个柱形图
			for(int i=1;i<m;i++)
				for(int j=0;j<n;j++){
					if(matrix[i][j]=='0')
						continue;
					else
						matrix[i][j]=(char) (matrix[i-1][j]+1);
		   }
			
			//获取面积
		   for(int i=0;i<m;i++)
			 for(int j=0;j<n;j++){
				if(matrix[i][j]=='0'){
					continue;
				}else{
					int min=matrix[i][j]-48;
					int k=j;
					for(;k<n;k++){
						if(matrix[i][k]=='0')
							break;
						else{
							if(min>matrix[i][k]-'0')
								min=matrix[i][k]-'0';
						   
							if(area<min*(k-j+1)){
								area=min*(k-j+1);                   					
							}	
						}
					}
				}
			}
		   return area;
	}

上图代码的求面积的算法是个迭代的遍历每一个都遍历一次

二、刷的另一道题

直接求解代码列状图的最大面积那么用上面的遍历后会超时的

public int largestRectangleArea(int[] height) {
    	  
    	  if(height.length==0)return 0;
          
    	  int max=height.length;
    	  
          for(int i=0;i<height.length;i++){
               if(height[i]==1){
            	   continue;
               }
        	  
        	  int minHeight=height[i];
        	  int j=i;
        	  for(;j<height.length;j++){
        		  if(height[j]<minHeight)
        			  minHeight=height[j];
        		  if(max<minHeight*(j-i+1))
        			  max=minHeight*(j-i+1);
        	  }
          }
          return max;
      }

第二种做法是什么那？

一个递增的柱状图他们求解一个最大的值

寻找每一个峰值，然后求解，抄的然后这部分高的和后面的比较没意思了，比较低的就可以了。

if(height.length==0){
		         return 0;
	     }
    	  Stack<Integer> stack=new Stack<Integer>();
    	 
    	  int max=0;
    	  int rightarea=0;
    	  int i=0;
    	  for(;i<height.length;i++){
    		  while(!stack.empty()&&height[stack.peek()]>height[i]){
    	            int index=stack.pop().intValue();

    	            rightarea=(stack.empty()?i:i-stack.peek()-1)*height[index];
    	            
    	            if(rightarea>max)max=rightarea;
    		  }
    		  stack.add(new Integer(i));
    	  }
    	  
    	  while(!stack.empty()){
	            int index=stack.pop().intValue();
	            rightarea=(stack.empty()?i:i-stack.peek()-1)*height[index];
	            if(rightarea>max)max=rightarea;
		  }
    	  return max;