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

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

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

思路:用栈,两个重要的逻辑。

  1. 只有当i的位置的值height[i]大头当前栈顶位置所代表的值(height[stack.peek()]),则i位置才可以压入stack。
  2. 如果当前的i的位置的值height[i]小于或者等于当前栈顶所代表的值(height[stack.peek()]),则把栈中存的位置不断弹出,直到栈顶所代表的值小于height[i],再把位置i压入栈。
  3. 那么弹出位置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. 以每一行做切割,统计以当前行作为低的情况下,每个位置往上的1的数量,使用高度数组height来表示。
  2. 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;
    }

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏待你如初见

Day10

1502
来自专栏云霄雨霁

Java--集合类之Collection与Map

2338
来自专栏算法与数据结构

数据结构 链表改进

主要介绍循环链表和双向循环链表 循环链表 双向循环链表 2-1 对于一非空的循环单链表,h和p分别指向链表的头、尾结点,则有() ? 循环单链表判空: 设头结点...

4747
来自专栏禁心尽力

Set容器--HashSet集合

Set容器特点: ①   Set容器是一个不包含重复元素的Collection,并且最多包含一个null元素,它和List容器相反,Set容器不能保证其元素的顺...

2225
来自专栏Android机器圈

递归 —— 二分查找法 —— 归并排序

二分法就是把一个数组折半查找,再折半直到找到数据位置,或者无数据位置。比如说1-100,你选的值是23,那么范围写法就是(索引写法类似)

1824
来自专栏有趣的Python

4-Java常用工具类-集合

问题: 存储20名学生的学生信息。20是不变的,就是这么多。 问题: 存储商品信息。不知道自己要买多少商品。

2162
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题15求链表中倒数第K个结点

算法的分析过程均在代码注释中: /** * 题目:输入一个单链表,输出该链表从后往前的第k个数。 * PS:从后往前数时从1开始计数。 * @author...

2996
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedHashMap

34914
来自专栏Hongten

java中的List记录是否完全匹配方法

===================================================

1051
来自专栏Java技术栈

Java集合从菜鸟到大神演变

先来看一张集合概况图,这里从上到下列举了几个最经常用的集合 ? 1、集合接口 java.util.Collection 是一个集合接口。它提供了对集合对象进行基...

4326

扫码关注云+社区

领取腾讯云代金券