NC237 最大矩形

参考的链接

import java.util.*;


public class Solution {
    public int maximalRectangle (int[][] matrix) {
        //调用length获得二维数组的行数n
        //求出二维数组的列数m
        int n=matrix.length;
        int m=matrix[0].length;
        //正向遍历每一行，逆向遍历列，求出每个元素的右边连续1的个数
        for(int i=0;i<n;i++){
            for(int j=m-2;j>=0;j--){
                  matrix[i][j]=matrix[i][j]==0?0:matrix[i][j]+matrix[i][j+1];
            }
        }
        int maxArea=0;
        int j=0;
        //遍历每一列，分别将每一列的不同行作为直方图，求出最大的矩形的面积
        while(j<m){
            int maxheight=0;
            int[] height=new int[n];
            //以每一列的每一行的元素作为直方图的底，求出每个直方图的高度，以及最大的直方图的高度
            for(int i=0;i<n;i++){
                height[i]=matrix[i][j];
                maxheight=Math.max(maxheight,height[i]);
            }
            //如果直方图的最大的高度为0，那么就表示不能形成矩形，直接以后一列的不同行的元素 作为底的直方图所能形成的最大的矩形
            if(maxheight==0){
                j++;
                continue;
            }
            //调用函数求出最大的矩形的面积
            maxArea=Math.max(maxArea,largestRectangleArea(height));
            j++;
        } 
        return maxArea;
    }
    //求出最大的矩形的面积
    private int largestRectangleArea(int[] height){
        //开一个栈
        Stack<Integer> stack=new Stack<>();
        int n=height.length;
        int maxArea=0;
       //遍历每一个高度
       //只要栈不为空并且后面入栈的元素小于栈顶的元素
       //就将栈顶记录的高度作为矩形的高，矩形的右边界就是即将入栈的元素i,矩形的左边界就是l
       //所以矩形的面积就是h*(i-l)
        for(int i=0;i<n;i++){
             while(!stack.empty()&&height[stack.peek()]>height[i]){
                int h=height[stack.pop()];
                int l=stack.empty()?0:stack.peek()+1;
                maxArea=Math.max(maxArea,h*(i-l));
             }
             stack.push(i);
        }
        //对于剩下的元素
        //只要栈不为空，就将栈顶的元素记录的高度作为矩形的高h
        //矩形的右边界就是n，左边界是l，矩形的面积=h*(n-l)
        while(!stack.empty()){
            int h=height[stack.pop()];
            int l=stack.empty()?0:stack.peek()+1;
            maxArea=Math.max(maxArea,h*(n-l));
        }
       return maxArea;
    }
}