LeetCode <Stack>84&85. Maximal Rectangle&Largest Rectangle in Histogram

原创

大学里的混子

修改于 2018-11-20 11:32:52

4010

修改于 2018-11-20 11:32:52

文章被收录于专栏：LeetCodeLeetCode

84.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

题目大意:求直方图的最大的面积。

思路：用栈，两个重要的逻辑。

只有当i的位置的值height[i]大头当前栈顶位置所代表的值（height[stack.peek()]）,则i位置才可以压入stack。
如果当前的i的位置的值height[i]小于或者等于当前栈顶所代表的值（height[stack.peek()]）,则把栈中存的位置不断弹出，直到栈顶所代表的值小于height[i]，再把位置i压入栈。
那么弹出位置j，所能扩大出来的最大的矩形为(i-k-1)*height[j]

解法：

public int largestRectangleArea(int[] height) {  
        if (height==null||height.length==0) return 0;
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0 ; i < height.length;i++){
            while (!stack.isEmpty() && height[i]<=height[stack.peek()]){
                int j = stack.pop();
                int k = stack.isEmpty()?-1:stack.peek();
                int curArea = (i-k-1)*height[j];
                maxArea = Math.max(curArea,maxArea);
            }
            stack.push(i);
        }
        //for循环执行完后，栈不为空，那么继续对栈中的元素处理，注意这个这个时候计算面积的逻辑为：
        // (height.length - k -1)*height[j];
        while (!stack.isEmpty()){
            int j = stack.pop();
            int k = stack.isEmpty()?-1:stack.peek();
            int curArea = (height.length - k -1)*height[j];
            maxArea = Math.max(maxArea,curArea);
        }
        return maxArea;
    }

注意：这里压入栈的是i的值，也就是直方图的横坐标的值，而不是纵坐标的值。

85. Maximal Rectangle

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

题目大意：最大全1的矩阵的大小。

思路：

以每一行做切割，统计以当前行作为低的情况下，每个位置往上的1的数量，使用高度数组height来表示。
1中的每一个情况下求最大的矩形。这转化为LeetCode《84.Largest Rectangle in Histogram》的问题。

解法：

public int maximalRectangle(char[][] matrix) {

        if (matrix.length==0||matrix[0].length == 0) return 0;
        int maxArea = 0;
        int[] height = new int[matrix[0].length];
     
        for (int i = 0;i<matrix.length;i++){
            for (int j = 0;j<matrix[0].length;j++){
                height[j] = matrix[i][j]-'0' ==0 ? 0 : height[j]+1;
                }
            maxArea = Math.max(maxArea,maxRecFromBottom(height));
    }
        return maxArea;
    }

    public int maxRecFromBottom(int[] height){
        if (height==null||height.length==0) return 0;
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0 ; i < height.length;i++){
            while (!stack.isEmpty() && height[i]<=height[stack.peek()]){
                int j = stack.pop();
                int k = stack.isEmpty()?-1:stack.peek();
                int curArea = (i-k-1)*height[j];
                maxArea = Math.max(curArea,maxArea);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()){
            int j = stack.pop();
            int k = stack.isEmpty()?-1:stack.peek();
            int curArea = (height.length - k -1)*height[j];
            maxArea = Math.max(maxArea,curArea);
        }
        return maxArea;
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

登录后参与评论

0 条评论

热度