1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
        int count = 0, max = properties[0][1];
        for (int i = 1; i < properties.length; i++) {
            if (properties[i][1] < max) {
                count += 1;
            }
            max = Math.max(max, properties[i][1]);
        }
        return count;
    }
}

首先就会想到把properties按照第0个元素给倒序sort一下. 如果两个property的第0个元素相同, 那么我们根据第1个元素大小倒序sort. 然后从前往后遍历. 我们维护一个变量, 来记录目前遇到的最大的properties[i][1], 如果当前的property的第1个元素小于这个max, 那么该pair就是weak的. 但是有edge case就是万一贡献这个max的pair拥有和当前pair一样值的第0个元素呢? 比如[5, 4], [5, 3]我们发现到[5, 3]时, max是4, 此时[5, 3]中的3小于4, 因此我们会认为该pair是weak的, 然而贡献这个4的pair的第0个元素是5, 这和当前pair的第0个元素相同, 因此[5, 3]不是weak的.

我们想要的是和在当前pair的左侧, 且第0个元素和当前pair不同的pairs中最大的properties[i][1]是什么. 那这怎么得到? 一个很巧妙的做法就是之前sort的时候, 如果两个property的第0个元素相同, 那么根据properties的第1个元素按照顺序sort. 这样的好处就是, 我们同样记录从左往后遍历时遇到的最大的properties[i][1]. 如果到达某个pair处发现该pair的第1个元素小于我们记录的max, 此时贡献该max的pair的第0个元素一定大于当前pair的第0个元素, 因为如果二者相同, 我们是按照它们第1个元素顺序排的, 贡献该max的pair又在当前pair的左侧, 此时贡献该max的pair的第一个元素应该小于等于当前pair的第一个元素才对, 因此此时与我们的假设冲突. 这样我们就能知道当前的pair左侧和自己第0个元素不同的pairs中最大的第一个元素是什么了. 很巧妙的方法. 和354俄罗斯套娃用的一样的手法.

时间复杂度: O(nlogn)
空间复杂度: O(logn) 因为用了sort.