社区首页 >专栏 >单调栈结构 && 84. Largest Rectangle in Histogram&&最大子矩阵的大小

单调栈结构 && 84. Largest Rectangle in Histogram&&最大子矩阵的大小

原创

大学里的混子

修改于 2019-02-25 03:00:17

54600

代码可运行

文章被收录于专栏：LeetCodeLeetCode

运行总次数：0

代码可运行

一、

二、 Largest Rectangle in Histogram 直方图的最大的面积

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

解法：

    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length < 1) return 0;
        //构建一个栈低到栈顶 由小到大的单调栈
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        for(int i = 0; i < heights.length; i++){
            //栈不为空，并且栈顶的元素大于当前的元素时候，弹出栈中的元素
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
                int j = stack.pop();
                int k = stack.isEmpty()? -1 : stack.peek();
                int curArea = (i - k - 1) * heights[j];
                maxArea = Math.max(maxArea,curArea);
            }
            stack.push(i);
        }
        //当遍历完整个数组，栈不为空，那么需要继续弹出，说明没有比栈顶元素更小的元素了
        while (!stack.isEmpty()){
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (heights.length - k - 1) * heights[j];
            maxArea = Math.max(maxArea,curArea);
        }
        return maxArea;
    }

另外一种采用数组模拟栈的写法，实际上与上面的解法一样，都是单调栈的解法

   public int largestRectangleArea(int[] heights) {
    int len = height.length;
        int[] s = new int[len+1];
        int top = 0;
        int maxArea = 0;
        for(int i = 0; i <= len; i++){
            int h = (i == len ? 0 : height[i]);
            while(top != 0&&height[s[top-1]] > h){ 
                int tp = s[top-1];
                top--;
                maxArea = Math.max(maxArea, height[tp] * (top==0 ? i : i - 1 - s[top-1]));
            }
            s[top++] = i;       
        }
        return maxArea;
    }

三、最大子矩阵的大小

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

解法：

 public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length < 1) return 0;
        //构建一个栈低到栈顶 由小到大的单调栈
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        for(int i = 0; i < heights.length; i++){
            //栈不为空，并且栈顶的元素大于当前的元素时候，弹出栈中的元素
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]){
                int j = stack.pop();
                int k = stack.isEmpty()? -1 : stack.peek();
                int curArea = (i - k - 1) * heights[j];
                maxArea = Math.max(maxArea,curArea);
            }
            stack.push(i);
        }
        //当遍历完整个数组，栈不为空，那么需要继续弹出，说明没有比栈顶元素更小的元素了
        while (!stack.isEmpty()){
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            int curArea = (heights.length - k - 1) * heights[j];
            maxArea = Math.max(maxArea,curArea);
        }
        return maxArea;
    }

    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int res = 0;
        int [] bottom = new int[matrix[0].length];

        for (int i = 0 ; i < matrix.length;i++){
            for (int j = 0 ; j < matrix[0].length ;j++)
            bottom[j] = matrix[i][j] == '0' ? 0 :bottom[j] + 1;
            res = Math.max(res,largestRectangleArea(bottom));
        }
        return res;

    }