Medium

题目描述

给你一个二维数组 points 和一个字符串 s，其中 points[i] 表示点 i 的坐标，s[i] 表示点 i 的标签。

一个有效的正方形是指以原点 (0, 0) 为中心，边与坐标轴平行，且不包含两个具有相同标签的点的正方形。

返回有效正方形中包含的最大点数。

注意：

  • 如果一个点位于正方形的边界上或内部，则认为该点在正方形内。
  • 正方形的边长可以为零。

示例 1：

输入：points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = "abdca"
输出：2
解释：边长为 4 的正方形包含两个点 points[0] 和 points[1]。

示例 2：

输入：points = [[1,1],[-2,-2],[-2,2]], s = "abb"
输出：1
解释：边长为 2 的正方形包含一个点，即 points[0]。

示例 3：

输入：points = [[1,1],[-1,-1],[2,-2]], s = "ccd"
输出：0
解释：无法创建以原点为中心的有效正方形，使其仅包含 points[0] 和 points[1] 中的一个点。

约束：

  • 1 <= s.length, points.length <= 10^5
  • points[i].length == 2
  • -10^9 <= points[i][0], points[i][1] <= 10^9
  • s.length == points.length
  • points 由不同的坐标组成
  • s 只包含小写英文字母

解题思路

解题思路

这道题需要找到以原点为中心的最大有效正方形，其中有效指的是不包含相同标签的点。

核心观察：

  1. 对于点 (x, y)，要被包含在以原点为中心的正方形内，正方形的边长至少需要 2 * max(abs(x), abs(y))
  2. 我们可以按照每个点到原点的"切比雪夫距离"（即 max(abs(x), abs(y))）进行排序
  3. 然后逐步扩大正方形，检查当前大小下是否出现重复标签

算法步骤：

  1. 计算每个点的切比雪夫距离，并与对应标签一起存储
  2. 按距离排序
  3. 使用二分查找或直接遍历，找到最大的有效正方形边长
  4. 在扩大正方形的过程中，用哈希表记录已出现的标签，一旦发现重复标签就停止

优化思路：

  • 可以直接遍历所有可能的边长，对于每个边长检查包含的点是否有重复标签
  • 也可以用二分查找优化，但由于需要检查标签重复性，直接遍历更简单

时间复杂度主要来自排序操作，为 O(n log n)。

代码实现

class Solution {
public:
    int maxPointsInsideSquare(vector<vector<int>>& points, string s) {
        int n = points.size();
        vector<pair<int, char>> distanceTag;
        
        // 计算每个点的切比雪夫距离并配对标签
        for (int i = 0; i < n; i++) {
            int dist = max(abs(points[i][0]), abs(points[i][1]));
            distanceTag.push_back({dist, s[i]});
        }
        
        // 按距离排序
        sort(distanceTag.begin(), distanceTag.end());
        
        unordered_set<char> used;
        int maxPoints = 0;
        
        for (int i = 0; i < n; i++) {
            char tag = distanceTag[i].second;
            
            // 如果当前标签已经使用过，停止
            if (used.count(tag)) {
                break;
            }
            
            used.insert(tag);
            maxPoints++;
        }
        
        return maxPoints;
    }
};

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        n = len(points)
        distance_tag = []
        
        # 计算每个点的切比雪夫距离并配对标签
        for i in range(n):
            dist = max(abs(points[i][0]), abs(points[i][1]))
            distance_tag.append((dist, s[i]))
        
        # 按距离排序
        distance_tag.sort()
        
        used = set()
        max_points = 0
        
        for dist, tag in distance_tag:
            # 如果当前标签已经使用过，停止
            if tag in used:
                break
            
            used.add(tag)
            max_points += 1
        
        return max_points

public class Solution {
    public int MaxPointsInsideSquare(int[][] points, string s) {
        int n = points.Length;
        var distanceTag = new List<(int dist, char tag)>();
        
        // 计算每个点的切比雪夫距离并配对标签
        for (int i = 0; i < n; i++) {
            int dist = Math.Max(Math.Abs(points[i][0]), Math.Abs(points[i][1]));
            distanceTag.Add((dist, s[i]));
        }
        
        // 按距离排序
        distanceTag.Sort((a, b) => a.dist.CompareTo(b.dist));
        
        var used = new HashSet<char>();
        int maxPoints = 0;
        
        foreach (var (dist, tag) in distanceTag) {
            // 如果当前标签已经使用过，停止
            if (used.Contains(tag)) {
                break;
            }
            
            used.Add(tag);
            maxPoints++;
        }
        
        return maxPoints;
    }
}

var maxPointsInsideSquare = function(points, s) {
    const n = points.length;
    const distanceTag = [];
    
    // 计算每个点的切比雪夫距离并配对标签
    for (let i = 0; i < n; i++) {
        const dist = Math.max(Math.abs(points[i][0]), Math.abs(points[i][1]));
        distanceTag.push([dist, s[i]]);
    }
    
    // 按距离排序
    distanceTag.sort((a, b) => a[0] - b[0]);
    
    const used = new Set();
    let maxPoints = 0;
    
    for (const [dist, tag] of distanceTag) {
        // 如果当前标签已经使用过，停止
        if (used.has(tag)) {
            break;
        }
        
        used.add(tag);
        maxPoints++;
    }
    
    return maxPoints;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log n)
空间复杂度O(n)
  • 时间复杂度：主要来自排序操作 O(n log n)，遍历过程为 O(n)
  • 空间复杂度：需要额外的数组存储距离和标签对，以及哈希表存储已使用的标签

相关题目