-
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; } };
-
leetcode最大矩形_[LeetCode] 223. 矩形面积
2020-12-31 16:13:57题目链接: https://leetcode-cn.com/problems/rectangle-area难度:中等通过率:41.3%题目描述:在 二维 平面上计算出两个 由直线构成的 矩形重叠后形成的总面积。每个矩形由其左下顶点和右上顶点坐标表示,如图所示...题目链接: 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 -
leetcode最大矩形_leetcode 85 最大矩形(c++)
2020-12-22 04:40:34###题目给定一个仅包含 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.lengthcols == matrix[0].length0 <= row, cols <= 200matrix[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矩阵中,最后以一行一行的顺序进行单调栈操作,通过每一行的最大的矩形面积更新全局最大矩形面积。读者可以试着在草稿纸上模拟,详细请看代码。 -
leetcode最大矩形_yiduobo的每日leetcode 85.最大矩形
2021-01-02 06:59:1185.最大矩形https://leetcode-cn.com/problems/maximal-rectangle/在完成了上一题之后,这一题的思路就比较简单了。我们可以从上往下,每次关注前k行。具体来说就是以第k行为基底,将竖着的连续的1看做上一题中的... -
leetcode最大矩形_[LeetCode] 85. 最大矩形
2021-01-05 12:22:48题目链接 : https://leetcode-cn.com/problems/maximal-rectangle/题目描述:给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积示例:输入: [ ["1","0","1","0","0"], ["1","0","1",... -
leetcode最大矩形_LeetCode刷题实战85: 最大矩形
2021-01-05 12:22:48所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做最大矩形,我们先来看题面:... -
leetcode最大矩形_yiduobo的每日leetcode 363.矩形区域不超过K的最大数值和
2021-01-05 12:22:46矩形区域不超过K的最大数值和https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/最朴素的做法当然是枚举左上角和右下角的坐标,然后计算其中的数值和并判断与k的大小情况,是O((mn)^2)的算法... -
leetcode最大矩形_LeetCode-python 85.最大矩形
2020-12-31 00:44:44题目链接难度:困难 类型:动态规划给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。示例输入:[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0... -
leetcode最大矩形_Leetcode题解 MaximalRectangle
2020-12-10 06:10:48点击上方“程序员大白”,选择“星标”公众号重磅干货,第一时间送达题目分析中文描述 只有 0 和 1 的二维矩阵,找出只包含 1 的最大矩形,返回最大矩形的面积。 举个例子,以下矩阵 matrix 1 0 1 0 01 0 1 1 11 1 1... -
leetcode最大矩形_leetcode84 柱状图中最大矩形
2021-01-13 07:54:58题目给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。image.png示例:输入: [2,1,5,6,2,3]输出: 10分析这题让我学会了一个经典... -
leetcode最大矩形_LeetCode-85. Maximal Rectangle
2020-12-17 10:40:11最大矩形题目难度:困难相关标签:栈数组动态规划哈希表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: ... -
leetcode最大矩形_[LeetCode] 363. 矩形区域不超过 K 的最大数值和
2021-01-05 12:22:47题目链接: https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k难度:困难通过率:34.1%题目描述:给定一个非空二维矩阵 matrix _和一个整数 _k ,找到这个矩阵内部不大于 k 的最大矩形和。... -
leetcode最大矩形_leetcode No.221 最大正方形
2021-01-05 12:22:46最大正方形 - 力扣(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最大矩形_LeetCode刷题实战84: 柱状图中最大的矩形
2020-12-04 06:15:27所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做柱状图中最大的矩形,我们先来看题面:... -
leetcode最大矩形_[LeetCode] 最大正方形
2021-01-05 12:22:46题目链接: 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最大矩形_LeetCode 84 hard 柱状图中最大的矩形 Python解题记录
2021-01-05 12:22:50今天我们做的题是力扣leetcode-cn.com题目给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。以上是柱状图的示例,其中每个... -
leetcode最大矩形_最大矩形(单调栈)
2021-01-05 12:22:46题目描述:LeetCode_85:最大矩形给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。 示例: 输入: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ... -
leetcode最大矩形_LeetCode 84. 柱状图中最大的矩形
2020-12-22 04:40:15题目描述给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。 以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5... -
leetcode最大矩形_[LeetCode] 84. 柱状图中最大的矩形
2021-01-05 12:22:48题目链接 : 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刷题实战91:解码方法
2021-01-05 12:22:48所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做解码方法,我们先来看题面:... -
leetcode最大矩形_LeetCode刷题实战89:格雷编码
2021-01-05 12:22:49所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做格雷编码,我们先来看题面:... -
leetcode最大矩形_LeetCode刷题实战86: 分隔链表
2021-01-05 12:22:47所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做分隔链表,我们先来看题面:... -
leetcode最大矩形_LeetCode刷题实战87: 扰乱字符串
2021-01-05 12:22:49所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做扰乱字符串,我们先来看题面:... -
leetcode最大矩形_LeetCode刷题实战93:复原IP地址
2021-01-05 12:22:48所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !今天和大家聊的问题叫做复原IP地址,我们先来看题面:... -
LeetCode:矩形区域【223】
2018-08-15 10:35:00LeetCode:矩形区域【223】 题目描述 在二维平面上计算出两个由直线构成的矩形重叠后形成的总面积。 每个矩形由其左下顶点和右上顶点坐标表示,如图所示。 示例: 输入:-3, 0, 3, 4, 0, -1, 9, 2输出:45 说明... -
leetcode最大矩形_LeetCode刷题笔记85:最大矩形(Python实现)
2021-01-13 07:54:55题目描述:给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。示例:输入:[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出: 6...