Question

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attack<sub>i</sub>, defense<sub>i</sub>] represents the properties of the i<sup>th</sup> character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character’s attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attack<sub>j</sub><span> </span>> attack<sub>i</sub> and defense<sub>j</sub><span> </span>> defense<sub>i</sub>.

Return the number of weak characters.

Solution

本题与354. Russian Doll Envelopes相近。

首先对数组进行排序，根据角色的attack数值降序排序，如果两者的attack数值相等，则根据两者的defence升序排序。

记录一个遍历过的最大defence数值maxDefence，遍历数组，如果当前maxDef大于角色的防御值，则此时当前遍历角色的attack与defence均严格小于上一个计算的角色，因此count加一。
否则更新maxDef。

*由于attack是降序的，因此可以确定遍历时下一组数组的attack一定更弱。（由于相同attack的角色是根据defence升序排列，因此记录maxDef时会逐个更新maxDef的值。）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        int count = 0, maxDef = Integer.MIN_VALUE;
            
        Arrays.sort(properties, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] == b[0]) return a[1] - b[1];
                return b[0] - a[0];
            }
        });
        
        for(int[] character : properties){
            if(maxDef > character[1]) count++;
            else maxDef = character[1];
        }
        return count;
    }
}

Question

You are given a 2D array of integers envelopes where envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Solution 1

最长递增子数列

这道题是LIS问题（Longest Increasing Subsequence） 的升级版。
后一个数组中的两个元素应该同时严格大于前一个数组中的两个元素。
因此我们需要维护一个宽度和高度同时严格单调递增的数列。

排序

我们可以对数组以宽度进行比较排序。当二者的宽度相等时，以高度的倒序排序。
（采用倒序排序是为了下面处理时排除不严格大于上一个数组的情况。）

递增数列

我们可以维护一个递增动态数组arr，记录高度组成的单调递增数列。（LIS）
首先将数组中的第一个元素的高度加入动态数组。
然后遍历数组envelopes[]：

• 如果当前数组的高度height大于单调递增数列的最大值：
  • 则当前的数组的宽度和高度均严格大于数组中最后一个高度对应的数组。
  • 数组是优先以宽度的顺序排列，相等时以高度的倒序排列。由于相同宽度时高度大的在前，因此当当前高度大于之前的最大高度，则宽度也一定大于之前的最大宽度。
• 如果小于或者等于单调递增数列的最大值：
  • 单调数列中高度的增长越平缓，我们在后面找到更多严格大于height的可能性就越大，因此可以用贪心思想，更新单调数列中的第一个大于当前高度的值。
  • 由于单调递增数列是有序的，因此可以采用二分搜索来寻找第一个大于当前高度的值的下标，并将其更新为当前的height。

排序的时间复杂度为O(nlogn)，遍历数组的时间复杂度为O(n)，二分搜索的时间复杂度为O(logn)。
总的时间复杂度为O(nlogn)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a,b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        List<Integer> arr = new ArrayList<>();
        arr.add(envelopes[0][1]);
        for(int i = 1; i < envelopes.length; i++){
            int height = envelopes[i][1];
            if(height > arr.get(arr.size()-1)){
                arr.add(height);
            }
            else{
                int index = Collections.binarySearch(arr, height);
                if(index < 0) index = -index-1;
                arr.set(index, height);
            }
        }
        return arr.size();
    }
}

Solution 2

注意这个方法在LeetCode中会超时，仅仅是记录一下思路，也可以采用动态规划的方法。
记忆化搜索剪枝。
记忆化搜索每个envelope。

memorazation()方法，返回当前的envelope中可以包含的最大数量。
当数组memo[i]不等于0时，返回memo[i]。
否则初始化最大值max为1。
遍历数组中的所有元素，如果宽度于长度都大于envelopes[i]，则向下递归搜索该元素。
比较并更新max和递归结果的返回值+1。
最后将当前位置memo[i]设置为包含的最大数量max。

遍历所有元素时间复杂度O(n)。
记忆化搜索元素的子项时间复杂度O(n)。
时间复杂度为O(n2)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    int[][] dolls;
    int[] memo;
    
    public int maxEnvelopes(int[][] envelopes) {
        dolls = envelopes;
        memo = new int[dolls.length];
        int res = 0;
        for(int i = 0; i < dolls.length; i++){
            if(memo[i] != 0) continue;
            memorazation(i);
            res = Math.max(res, memo[i]);
        }
        return res;
    }
    
    private int memorazation(int i){
        if(memo[i] != 0){
            return memo[i];
        }
        int max = 1;
        for(int k = 0; k < dolls.length; k++){
            if(dolls[k][0] < dolls[i][0] && dolls[k][1] < dolls[i][1]){
                max = Math.max(max, memorazation(k) + 1);
            }
        }
        return memo[i] = max;
    }
}