题目描述：



思路：除去四种不相交的情况；（上下左右）
代码如下：
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%
题目描述:
在 二维 平面上计算出两个 由直线构成的 矩形重叠后形成的总面积。
每个矩形由其左下顶点和右上顶点坐标表示，如图所示。
示例:
输入: -3, 0, 3, 4, 0, -1, 9, 2
输出: 45
说明: 假设矩形面积不会超出  int  的范围。
思路:
这道题，把问题考虑清楚就不难了！
首先，我们调整两个矩形，让第一个矩形是靠最左边的；
其次，先考虑没有重叠的情况，有三种情况，如图所示：
rectangle1的下边都大于（等于）rectangle2的上边，即 B >= H
rectangle1的右边都小于（等于）rectangle2的左边，即 C >= E
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

###题目
给定一个仅包含 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;
}
};

最大矩形
题目描述：

给定一个仅包含 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矩阵中，最后以一行一行的顺序进行单调栈操作，通过每一行的最大的矩形面积更新全局最大矩形面积。读者可以试着在草稿纸上模拟，详细请看代码。