leetcode2975. 移除栅栏得到的正方形田地的最大面积

2024-01-02 22:02:34

?题目

有一个大型的?(m - 1) x (n - 1)?矩形田地,其两个对角分别是?(1, 1)?和?(m, n)?,田地内部有一些水平栅栏和垂直栅栏,分别由数组?hFences?和?vFences?给出。

水平栅栏为坐标?(hFences[i], 1)?到?(hFences[i], n),垂直栅栏为坐标?(1, vFences[i])?到?(m, vFences[i])?。

返回通过?移除?一些栅栏(可能不移除)所能形成的最大面积的?正方形?田地的面积,或者如果无法形成正方形田地则返回?-1

由于答案可能很大,所以请返回结果对?109 + 7?取余?后的值。

注意:田地外围两个水平栅栏(坐标?(1, 1)?到?(1, n)?和坐标?(m, 1)?到?(m, n)?)以及两个垂直栅栏(坐标?(1, 1)?到?(m, 1)?和坐标?(1, n)?到?(m, n)?)所包围。这些栅栏?不能?被移除。

示例 1:

输入:m = 4, n = 3, hFences = [2,3], vFences = [2]
输出:4
解释:移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。

示例 2:

输入:m = 6, n = 7, hFences = [2], vFences = [4]
输出:-1
解释:可以证明无法通过移除栅栏形成正方形田地。

提示:

  • 3 <= m, n <= 109
  • 1 <= hFences.length, vFences.length <= 600
  • 1 < hFences[i] < m
  • 1 < vFences[i] < n
  • hFences?和?vFences?中的元素是唯一的。

Problem: https://leetcode.cn/problems/maximum-squar100169 e-area-by-removing-fences-from-a-field/description/

[TOC]

思路

遍历所有的横向栏杆与纵向栏杆,算出横向栏杆之间的差和纵向栏杆之间的差并存储两个集合,最终的答案就是两个集合的交集的平方

复杂度

时间复杂度:

O(m^2+n^2)

空间复杂度:

O(m+n)

Code

class Solution:
    def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int:
        
        ans = -1
        hFences.append(m)
        hFences.insert(0,1)

        row = set()
        for i in range(len(hFences)):
            for j in range(0,i):
                row.add(abs( hFences[i] - hFences[j] ))
                    
        vFences.append(n)
        vFences.insert(0,1)

        col = set()
        for i in range(len(vFences)):
            for j in range(0,i):
                col.add(abs(vFences[i] - vFences[j]))
                
                if abs(vFences[i] - vFences[j]) in row :
                    ans = max(ans,pow(abs(vFences[i] - vFences[j]),2))

        for val in row:
            if val in col:
                ans = max(ans,pow(val,2))
       
        return ans % 1_000_000_007 if 

文章来源:https://blog.csdn.net/qq_51118755/article/details/135329846
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。