leetcode85-最大矩形

原题

给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

示例:

输入:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"] ] 输出: 6

解法

思想

这道题可以分解成若干leetcode84-柱状图中最大的矩形的子问题,可以使用相同的方法。

我们从上往下动态规划二维数组,每增加一行就会出现不同的柱状区域。

leetcode85-最大矩形

从每一次得到的最大矩形面积中获取最大值,就是该题的答案

代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        if(length==0) return 0;
        int max = 0;
        int left[] = new int[length];
        int right[] = new int[length];
        left[0] = -1;
        right[length-1] = length;
        for(int i = 1;i<length;i++){
            //如果左边一列比当前列矮,则left就等于左边一列的下标。
            if(heights[i]>heights[i-1]) left[i] = i-1;
            else{
                //否则沿着左边这列的left一直查找过去,直到找到比当前列低的一列
                left[i] =  left[i-1];
                while(left[i]!=-1&&heights[left[i]]>=heights[i])
                    left[i] = left[left[i]];
            }
        }
        for(int i = length-2;i>=0;i--){
            //如果右边一列比当前列矮,则right就等于右边一列的下标。
            if(heights[i]>heights[i+1]) right[i] = i+1;
            else{
                //否则沿着右边这列的right一直查找过去,直到找到比当前列低的一列
                right[i] =  right[i+1];
                while(right[i]!=length&&heights[right[i]]>=heights[i])
                    right[i] = right[right[i]];
            }
        }
        for(int i = 0;i<length;i++){
            int area = (right[i]-left[i]-1)*heights[i];
            if(area>max) max = area;
        }
        return max;
    }
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length == 0) return 0;
        int height[] = new int[matrix[0].length];
        int max = 0;
        for(char[] line:matrix){
            //每增加一行改变height数组
            for(int i=0;i<line.length;i++){
                if(line[i]=='0') height[i]=0;
                else height[i] += 1;
            }
            int area = largestRectangleArea(height);
            if(area>max) max=area;
        }
        return max;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode85-%e6%9c%80%e5%a4%a7%e7%9f%a9%e5%bd%a2/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月24日 03:01
下一篇 2020年1月25日

相关推荐

  • leetcode108-将有序数组转换为二叉搜索树

    原题 将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数…

    算法 2020年1月18日
    080
  • leetcode260-只出现一次的数字III

    原题 给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。 示例: 输入: [1,2,1,3,2,5] 输出: [3,5…

    算法 2020年4月28日
    0140
  • leetcode209-长度最小的子数组

    原题 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例: 输入: s = …

    算法 2019年11月20日
    0160
  • leetcode173-二叉搜索树迭代器

    原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例: BSTIterator iterator…

    2020年1月16日
    050
  • leetcode103-二叉树的锯齿形层次遍历

    原题 给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。 例如:给定二叉树: [3,9,20,null,nul…

    算法 2020年1月25日
    060
  • leetcode98-验证二叉搜索树

    原题 给定一个二叉树,判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征: 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和…

    算法 2020年1月15日
    0120
  • leetcode454-四数相加II

    原题 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。 为…

    算法 2019年12月27日
    070
  • leetcode63-不同路径II

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月22日
    0130
  • leetcode19-删除链表的倒数第N个节点

    原题 给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。 示例: 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为…

    算法 2019年12月15日
    090
  • leetcode503-下一个更大元素II

    原题 给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序,这个数字之后的第一个比它更大的数,…

    算法 2020年2月1日
    090

发表回复

登录后才能评论