企业官网建设流程全解析

宁夏网站营销推广,wordpress多重筛选并排序,网站焦点图多少钱,农村自建房设计图app题目信息 平台#xff1a;LeetCode题目#xff1a;3047. 求交集区域内的最大正方形面积难度#xff1a;Medium题目链接#xff1a;Find the Largest Area of Square Inside Two Rectangles 题目描述 给定若干轴对齐矩形#xff08;用左下角与右上角坐标表示#xff09;…题目信息平台LeetCode题目3047. 求交集区域内的最大正方形面积难度Medium题目链接Find the Largest Area of Square Inside Two Rectangles题目描述给定若干轴对齐矩形用左下角与右上角坐标表示任选两矩形取它们的重叠区域。在所有重叠区域中求能放下的最大正方形面积。初步思路两矩形的交集仍是一个轴对齐矩形其宽高可由区间交得出。交集矩形中最大正方形边长等于min(交集宽, 交集高)面积为边长平方。枚举所有矩形对更新最大面积即可。算法分析核心枚举矩形对计算交集宽高并取最小值作为正方形边长技巧交集宽高为min(tx1, tx2) - max(bx1, bx2)与min(ty1, ty2) - max(by1, by2)正确性简述任意两矩形的交集范围唯一交集内能放下的最大正方形边长由更短边决定枚举所有矩形对即可覆盖全局最优时间复杂度O(n^2)空间复杂度O(1)代码实现C#includebits/stdc.husingnamespacestd;classSolution{public:longlonglargestSquareArea(vectorvectorintbottomLeft,vectorvectorinttopRight){longlongmax_side0;intn(int)bottomLeft.size();for(inti0;in;i){for(intj0;ji;j){intbx1bottomLeft[i][0],by1bottomLeft[i][1];inttx1topRight[i][0],ty1topRight[i][1];intbx2bottomLeft[j][0],by2bottomLeft[j][1];inttx2topRight[j][0],ty2topRight[j][1];intwidthmin(tx1,tx2)-max(bx1,bx2);intheightmin(ty1,ty2)-max(by1,by2);intsidemin(width,height);if(side0)max_sidemax(max_side,(longlong)side);}}returnmax_side*max_side;}};测试用例输入输出说明bottomLeft [[1,1],[2,2]], topRight [[3,3],[4,4]]1交集为 1x1最大正方形面积 1bottomLeft [[0,0],[1,0]], topRight [[2,1],[3,2]]0交集高度为 0无法放正方形bottomLeft [[0,0],[2,1],[3,3]], topRight [[3,3],[4,4],[5,5]]1取最优矩形对得到边长 1总结与反思交集矩形的最大正方形边长由短边决定先算交集再取最小值即可。枚举矩形对即可覆盖全局最优注意side 0才是有效交集。