[Leetcode] Rectangle Area 矩形面积

Cheng_Gang 发布于2019-08-14 12:26 / 1467人阅读

摘要：数学法复杂度时间空间思路基本的数学题，考察的是我们能否全面的考虑到所有可能。如果两个矩形没有重叠部分，则直接计算两个矩形面积之和就行了。因为两个矩形的坐标都可能比对方小，所以我们一共有四种可能情况是不重叠的。

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Rectangle Area Assume that the total area is never beyond the maximum possible value of int.

数学法 复杂度

时间 O(N) 空间 O(1)

思路

基本的数学题，考察的是我们能否全面的考虑到所有可能。如果两个矩形没有重叠部分，则直接计算两个矩形面积之和就行了。如果两个矩形有重叠部分，则要将重叠部分减去。如何判断两个矩形没有重叠部分呢，如果一个矩形右上角的横坐标比另一个矩形左下角的横坐标要小，或者一个矩形右上角的纵坐标比另一个矩形左下角的纵坐标要小，则两个矩形是不重叠的。因为两个矩形的坐标都可能比对方小，所以我们一共有四种可能情况是不重叠的。如果重叠的话，计算重叠部分面积就是四个横坐标中中间那两个和四个纵坐标中间那两个。

代码

public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int dup = 0;
        if(C < E || G < A || D < F || H < B){
            dup = 0;
        } else {
            int[] x = {A, C, E, G};
            int[] y = {B, D, F, H};
            Arrays.sort(x);
            Arrays.sort(y);
            dup = (x[2] - x[1]) * (y[2] - y[1]);
        }
        return (C - A) * (D - B) + (G - E)*(H - F) - dup;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64477.html

leetcode363. Max Sum of Rectangle No Larger Than K

摘要：思路一暴力循环如果我们将矩阵中的每个子矩阵都枚举出来，并计算其元素和，从而得出小于的最大值即可。题目要求 Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k. E...

nemo 2019-08-16 17:57 评论0 收藏0
Largest Rectangle in Histogram

摘要：而最大的矩形一定满足两个边界的高度小于该矩形的高度这个条件如果不满足的话，边界也可以被添加进来计算而不破坏矩形的形状，此时不为最大，因此找出所有这样的矩形就一定可以在其中找出面积最大的矩形。 Problem Given n non-negative integers representing the histograms bar height where the width of e...

vvpvvp 2019-07-24 17:33 评论0 收藏0
[Leetcode] Largest Rectangle (in Histogram) 最大矩形

摘要：以此类推，如果一直到栈为空时，说明刚出来的竖条之前的所有竖条都比它自己高，不然不可能栈为空，那我们以左边全部的宽度作为长方形的宽度。 Largest Rectangle in Histogram Given n non-negative integers representing the histograms bar height where the width of each bar...

邹强 2019-08-14 12:24 评论0 收藏0
leetcode84. Largest Rectangle in Histogram

摘要：题目要求即找到图中可以组合而成的面积最大的矩形。从而我们可以知道该矩形在水平方向上的最大扩展程度。也就是说，栈中数据记录了最远左侧下标，而当前的矩形则是最远右侧下标。当我们不采用数据结构时，寻找和计算的过程需要的时间复杂度。题目要求 Given n non-negative integers representing the histograms bar height where t...

Harpsichord1207 2019-08-15 10:55 评论0 收藏0
leetcode85. Maximal Rectangle

摘要：题目要求输入一个二维数组，其中代表一个小正方形，求找到数组中最大的矩形面积。思路一用二维数组存储临时值的一个思路就是通过存储换效率。从而省去了许多重复遍历，提高效率。这里我使用两个二维数组来分别记录到为止的最大长度和最大高度。题目要求 Given a 2D binary matrix filled with 0s and 1s, find the largest rectangle ...

jhhfft 2019-08-15 11:04 评论0 收藏0