精华内容
下载资源
问答
  • 836 LeetCode 矩形重叠

    2020-02-22 12:02:20
    题目描述: 思路:除去四种不相交的情况;(上下左右) 代码如下: class Solution { public: bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) { if((rec1[3]<=rec2[1])|...

    题目描述:
    在这里插入图片描述
    思路:除去四种不相交的情况;(上下左右)在这里插入图片描述

    代码如下:

    class Solution {
    public:
        bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
            if((rec1[3]<=rec2[1])||(rec1[2]<=rec2[0])||(rec1[0]>=rec2[2])||(rec1[1]>=rec2[3]))
            return false;
            return true;
        }
    };
    
    展开全文
  • 题目链接: https://leetcode-cn.com/problems/rectangle-area难度:中等通过率:41.3%题目描述:在 二维 平面上计算出两个 由直线构成的 矩形重叠后形成的总面积。每个矩形由其左下顶点和右上顶点坐标表示,如图所示...

    044d13d4a3cb148bbee8476ccb2754da.png

    题目链接: https://leetcode-cn.com/problems/rectangle-area

    难度:中等

    通过率:41.3%

    题目描述:

    二维 平面上计算出两个 由直线构成的 矩形重叠后形成的总面积。

    每个矩形由其左下顶点和右上顶点坐标表示,如图所示。

    0540c2ca55da421918933ccb9f65bb98.png

    示例:

    输入: -3, 0, 3, 4, 0, -1, 9, 2
    输出: 45

    说明: 假设矩形面积不会超出 int 的范围。

    思路:

    这道题,把问题考虑清楚就不难了!

    首先,我们调整两个矩形,让第一个矩形是靠最左边的;

    其次,先考虑没有重叠的情况,有三种情况,如图所示:

    75fd7de3bbeaf2772f6f58eb438b12e9.png
    1. rectangle1的下边都大于(等于)rectangle2的上边,即 B >= H
    2. rectangle1的右边都小于(等于)rectangle2的左边,即 C >= E
    3. rectangle1的上边都小于(等于)rectangle2的下边,即 B >= H

    最后, 要考虑重叠的情况,这种其实很好考虑,因为一定有重叠,所以可以找到上下左右边界

    上边界,取两个矩形的上边界的最小值

    下边界,取两个矩形的下边界的最大值

    左边界,取两个矩形的左边界的最大值

    右边界,取两个矩形的右边界的最小值

    得到重叠面积,只需要两个矩形相加减去重叠面积即可!


    有疑惑的地方,要留言哦~

    代码:

    class Solution:
        def computeArea(self, A: int, B: int, C: int, D: int, E: int, F: int, G: int, H: int) -> int:
            # 调整两个矩形位置, 让第一个矩形靠最左边
            if A > E:
                return self.computeArea(E, F, G, H, A, B, C, D)
            # 没有重叠的情况
            if B >= H or D <= F or C <= E:
                return abs(A - C) * abs(B - D) + abs(E - G) * abs(F - H)
            # 重叠情况
            # xia
            down = max(A, E)
            # shang
            up = min(C, G)
            # zuo
            left = max(B, F)
            # you
            right = min(D, H)
            return abs(A - C) * abs(B - D) + abs(E - G) * abs(F - H) - abs(up - down) * abs(left - right)

    更多题解:

    九四干:[LeetCode] 题目汇总(持续更新)zhuanlan.zhihu.com
    f4f36167f0149c71636ebfb5ddb50482.png

    8534c44122327124e5ec36ea441d8abf.png
    展开全文
  • ###题目给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。["1","0","1","0","0"]["1","0","1","1","1"]["1","1","1","1","1"]["1","0","0","1","0"]输出: 6###思路万物皆可动态规划...

    ###题目

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

    ["1","0","1","1","1"]

    ["1","1","1","1","1"]

    ["1","0","0","1","0"]

    输出: 6

    ###思路

    万物皆可动态规划,设置二维dp矩阵,其中dp[i][j]代表在第i行中包含第j个元素的最长的连续'1'的长度。例如[1,1,0,0,1,1,0,1],相应的dp矩阵的值为[1,2,0,0,1,2,0,1]。

    下一步开始遍历整个矩阵,遍历每一个元素的同时更新dp,同时计算最大面积,最大面积的计算原理是这样的假设dp[i][j]的值为5,只考虑第i行且带上matrix[i][j]时能组成的最大矩阵面积为5,高为1,底为

    再考虑上i-1行且带上matrix[i-1][j],此情况下能组成的最大矩形的高为2,底为

    再考虑上i-1行且带上matrix[i-2][j],此情况下能组成的最大矩形的高为3,底为

    一直到第0行,此情况下的最大矩形的高为i+1,底为

    通过上面的计算方式,考虑了所有的能够组成的矩形,那么matrix能够组成的最大矩形肯定会被计算一次,所以能够找出最大矩形面积,其实也算是暴力法,不过利用了dp数组保存下来的信息可以减少很多冗余计算。

    ###code

    class Solution {

    public:

    int maximalRectangle(vector>& matrix) {

    if(matrix.empty())return 0;

    int row=matrix.size(),col=matrix[0].size();

    vector>dp(row,vector(col,0));

    int maxarea=0;

    for(int i=0;i

    {

    for(int j=0;j

    {

    if(matrix[i][j]=='1')

    dp[i][j]= j==0 ? 1:dp[i][j-1]+1;

    int width=dp[i][j];

    for(int z=i;z>=0;--z)

    {

    if(dp[z][j]==0)//如果为0,那么后续所有的计算结果都为0,没必要算了 break;

    width=min(dp[z][j],width);//找出最小长度作为宽 maxarea=max(maxarea,width*(i-z+1));

    }

    }

    }

    return maxarea;

    }

    };

    ###思路

    官方题解这个思路还是666呀,将这个矩形转换成一个柱状图,这样就可以用84题的解法了。newbie:leetcode 84 柱状图中的最大的矩形(c++)​zhuanlan.zhihu.com

    例如:matrix=[1,1,1,1],[0,1,1,0],[0,0,1,1]

    matrix[0]、matrix[0]和matrix[1]、matrix[0]和matrix[1]和matrix[2]转换成leetcode 84要求的柱形图分别是[1,1,1,1]、[0,2,2,0]、[0,0,3,1]。

    分别求出上面三个柱形的最大面积即可。

    ###code

    class Solution {

    public:

    int max_area_f(vectorheights)

    {

    stacks;

    s.push(-1);//加上方便计算 int max_res=0;

    for(int i=0;i

    {

    while(s.top()!=-1&&heights[i]<=heights[s.top()])

    {

    int index=s.top();

    s.pop();

    max_res=max(max_res,heights[index]*(i-s.top()-1));

    }

    s.push(i);

    }

    while(s.top()!=-1)

    {

    int index=s.top();

    s.pop();

    max_res=max(max_res,heights[index]*(int(heights.size())-s.top()-1));

    }

    return max_res;

    }

    int maximalRectangle(vector>& matrix) {

    if(matrix.empty())return 0;

    int row=matrix.size(),col=matrix[0].size();

    vectordp(col,0);

    int max_area=0;

    for(int i=0;i

    {

    for(int j=0;j

    dp[j]= matrix[i][j]=='0'?0:dp[j]+1;

    max_area=max(max_area,max_area_f(dp));

    }

    return max_area;

    }

    };

    ###思路

    这个方法的出发点是,某一个元素不断向上方遍历,直到遇到“0”,以此找到其能组成的矩形的最大高度h,然后向左右两边扩展,扩展组成的矩形要满足高度为h,最大面积矩形肯定是这样组成的。

    因为假如有一个最大矩形,它的高为h,左边界 l,右边界 r,那么在矩形的底这一行的区间[l, r]内必然存在一点,包括它自己在内以及它上方的1的个数为h个,这一个点就是我们第一段所找出的那个元素。假设不存在这样的点,那么肯定有矩形的底这一行[l, r]范围内所有的元素的高度均大于h,那肯定是可以通过延伸高度来生成更大的矩形,因此该矩形不是最大矩形,所以可以证明第一段说的那个元素存在。

    所以,对于每个点,只需要计算出它的h、l、r,然后再算面积并不断更新最大面积就可以了。在遍历过程中,我个人觉得最难理解的地方就是如何更新right、left。对于height,它的更新只需要判断matrix[i][j]是否为1,如果为1,那么height的值为matrix[i-1][j]的height加1即可,如不为1,height为零。

    对于left,如果matrix[i][j]为1,那么left的值为matrix[i-1][j]的left值与cur_left中的最大值,其中cur_left为此行中的上一个0的序号加一,代表左边不可能扩展过此列;如果matrix[i][j]为0,那么它的left为0,这是因为当matrix[i][j]为0时,height为0,所以left的值取多少,计算出的面积都是0,但它必须小于等于0,不然会影响它的下一个元素的left的取值,因为某元素的的上一行的对应元素的left过大,就表明它限制了左延的边界,但其实当其为0时,其并不能够限制左延的边界再将cur_left设为j+1,代表遇到0了。

    对于right,如果matrix[i][j]为1,那么right的值为matrix[i-1][j]的right值与cur_right中的最小值,其中cur_right为此行中的后面的第一个0的序号减一,代表右边不可能扩展过此列;如果matrix[i][j]为0,那么它的right为n-1,这是因为当matrix[i][j]为0时,height为0,所以right的值取多少,计算出的面积都是0,但它必须大于等于matrix的列数,不然会影响它的下一个元素的right的取值,将cur_left设为j-1,代表遇到0了。

    最后计算面积为

    ,不断更新就可以了。

    ###code

    class Solution {

    public:

    int maximalRectangle(vector>& matrix) {

    if(matrix.empty()) return 0;

    int row = matrix.size();

    int col = matrix[0].size();

    vectorleft(col,0);

    vectorright(col,col);

    vectorheight(col,0);

    int maxarea = 0;

    for(int i = 0; i < row; i++)

    {

    int cur_left = 0, cur_right = col-1;

    // update height for(int j = 0; j < col; ++j) {

    if(matrix[i][j] == '1') height[j]++;

    else height[j] = 0;

    }

    // update left for(int j=0; j

    if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);

    else {left[j]=0; cur_left=j+1;}

    }

    // update right for(int j = col - 1; j >= 0; --j) {

    if(matrix[i][j] == '1') right[j] = min(right[j], cur_right);

    else {right[j] = col-1; cur_right = j-1;}

    }

    // update area for(int j = 0; j

    maxarea = max(maxarea, (right[j] - left[j]+1) * height[j]);

    }

    }

    return maxarea;

    }

    };

    展开全文
  • Leetcode 最大矩形

    2021-02-21 19:17:50
    最大矩形 题目描述: 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 提示:    rows == matrix.length    cols == ...

    最大矩形

    题目描述:

    给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
    提示:
       rows == matrix.length
       cols == matrix[0].length
       0 <= row, cols <= 200
       matrix[i][j] 为 '0' 或 '1'

    题目链接

    示例

    在这里插入图片描述

    输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
    输出:6
    解释:最大矩形如上图所示。
    class Solution {
        public int maximalRectangle(char[][] matrix) {
            int row = matrix.length;
            if(row == 0) return 0;
            int col = matrix[0].length;
            // 初始化
            int[][] heights = new int[row][col];
            for(int i = 0 ; i<col ; i++){
                for(int j = row-1 ; j>=0 ; j--){
                    if(matrix[j][i] == '1'){
                        heights[j][i] = ((j == row-1)?0:(heights[j+1][i]))+1;
                    }
                }
            }
            int max = 0;
            for(int i = 0 ; i<row ; i++){ // 遍历每一行
                int temp = largestRectangleArea(heights[i]);
                max = (max>temp)?max:temp;
            }
            return max;
        }
        private int largestRectangleArea(int[] heights) {
            int len = heights.length;
            if(len == 0) return 0;
            if (len == 1) return heights[0];
    
            int result = 0;
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < len; i++) {
                while (!stack.empty() && heights[i] < heights[stack.peek()]) { // 如果当前遍历下标的高度严格小于下标为栈顶的元素高度
                    int curHeight = heights[stack.pop()];
                    while (!stack.empty() && heights[stack.peek()] == curHeight) { // 相等情况下去重
                        stack.pop();
                    }
    
                    int curWidth;
                    if (stack.empty()) {
                        curWidth = i;
                    } else {
                        curWidth = i - stack.peek() - 1;
                    }
                    result = Math.max(result, curHeight * curWidth);
                }
                stack.push(i);
            }
            // 最终处理
            while (!stack.empty()) {
                int curHeight = heights[stack.pop()];
                while (!stack.empty() && heights[stack.peek()] == curHeight) {
                    stack.pop();
                }
                int curWidth;
                if (stack.empty()) {
                    curWidth = len;
                } else {
                    curWidth = len - stack.peek() - 1;
                }
                result = Math.max(result, curHeight * curWidth);
            }
            return result;
        }
    }
    

    该题本质上就是单调栈的应用,读者可以首先理解完该题,再来解决此题。
    首先我们需要进行预处理,即对matrix矩阵每一列的连续1的个数记录到heights矩阵中,最后以一行一行的顺序进行单调栈操作,通过每一行的最大的矩形面积更新全局最大矩形面积。读者可以试着在草稿纸上模拟,详细请看代码。

    展开全文
  • 85.最大矩形https://leetcode-cn.com/problems/maximal-rectangle/在完成了上一题之后,这一题的思路就比较简单了。我们可以从上往下,每次关注前k行。具体来说就是以第k行为基底,将竖着的连续的1看做上一题中的...
  • 题目链接 : https://leetcode-cn.com/problems/maximal-rectangle/题目描述:给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积示例:输入: [ ["1","0","1","0","0"], ["1","0","1",...
  • 所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做最大矩形,我们先来看题面:...
  • 矩形区域不超过K的最大数值和https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/最朴素的做法当然是枚举左上角和右下角的坐标,然后计算其中的数值和并判断与k的大小情况,是O((mn)^2)的算法...
  • 题目链接难度:困难 类型:动态规划给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。示例输入:[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0...
  • 点击上方“程序员大白”,选择“星标”公众号重磅干货,第一时间送达题目分析中文描述 只有 0 和 1 的二维矩阵,找出只包含 1 的最大矩形,返回最大矩形的面积。 举个例子,以下矩阵 matrix 1 0 1 0 01 0 1 1 11 1 1...
  • 题目给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。image.png示例:输入: [2,1,5,6,2,3]输出: 10分析这题让我学会了一个经典...
  • 最大矩形题目难度:困难相关标签:栈数组动态规划哈希表Description:Given a 2D binary matrix filled with 0's and 1s, find the largest rectangle containing only 1's and return its area.Example:Input: ...
  • 题目链接: https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k难度:困难通过率:34.1%题目描述:给定一个非空二维矩阵 matrix _和一个整数 _k ,找到这个矩阵内部不大于 k 的最大矩形和。...
  • 最大正方形 - 力扣(LeetCode)​leetcode-cn.com题目描述:在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。示例:输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 输出: 4解题...
  • 所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做柱状图中最大的矩形,我们先来看题面:...
  • 题目链接: https://leetcode-cn.com/problems/maximal-square难度:中等通过率:38.2%题目描述:在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。示例:输入: 1 0 1 0 0 1 0 1 1 1 1 1...
  • 今天我们做的题是力扣​leetcode-cn.com题目给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。以上是柱状图的示例,其中每个...
  • 题目描述:LeetCode_85:最大矩形给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例: 输入: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ...
  • 题目描述给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。 以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5...
  • 题目链接 : https://leetcode-cn.com/problems/largest-rectangle-in-histogram/题目描述:给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形...
  • 492 LeetCode 构造矩形

    2019-12-10 21:03:26
    题目描述: 思路:根据题目描述:有两个要求:1是长×宽=面积(L×K=area);2是长和宽的差值尽可能的小; 在一个循环 i 里面,范围是sqrt(area);当area能整除 i 时,赋值长和宽,当长小于宽时,结束循环; 代码...
  • 所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做解码方法,我们先来看题面:...
  • 所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做格雷编码,我们先来看题面:...
  • 所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做分隔链表,我们先来看题面:...
  • 所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做扰乱字符串,我们先来看题面:...
  • 所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做复原IP地址,我们先来看题面:...
  • LeetCode矩形区域【223】 题目描述 在二维平面上计算出两个由直线构成的矩形重叠后形成的总面积。 每个矩形由其左下顶点和右上顶点坐标表示,如图所示。 示例: 输入:-3, 0, 3, 4, 0, -1, 9, 2输出:45 说明...
  • 题目描述:给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。示例:输入:[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出: 6...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 796
精华内容 318
关键字:

leetcode矩形题目