LeetCode 3143 正方形中的最多点数

方法1：维护次最小值

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        Min1 = [inf] * 26; Min2 = inf
        for (x, y), c in zip(points, s):
            idx = ord(c) - ord('a'); d = max(abs(x), abs(y))
            if d < Min1[idx]:
                Min2 = min(Min2, Min1[idx])
                Min1[idx] = d
            elif d < Min2:
                Min2 = d
        return sum(d < Min2 for d in Min1)

class Solution {
    public int maxPointsInsideSquare(int[][] points, String s) {
        // Min1 中为每个字符距离原点的最小值
        int[] Min1 = new int[26]; Arrays.fill(Min1, Integer.MAX_VALUE);
        // Min2 为每个字符距离原点的次最小值中的最小值
        int Min2 = Integer.MAX_VALUE, n = points.length;
        for(int i = 0; i < n; i++) {
            int x = points[i][0], y = points[i][1], idx = s.charAt(i) - 'a';
            int d = Math.max(Math.abs(x), Math.abs(y));
            if(Min1[idx] > d) {  // d 为字符 idx 距离的最小值
                Min2 = Math.min(Min2, Min1[idx]);
                Min1[idx] = d;
            } else if (Min2 > d) {  // d 为所有字符距离的次最小值
                Min2 = Math.min(Min2, d);
            }
        }
        int ans = 0;
        for(int d : Min1) { // 对于每个字符
            if(Min2 > d) ans++; // 判断当前字符是否小于次最小值
        }
        return ans;
    }
}