朴素的思路-俄罗斯套娃

发表于 | |
字数统计: 977 | 阅读时长 ≈ 3

题意提取

信封有两属性，宽（w），高（h）;
信封a套入信封b的要求: w[a] < w[b] && h[a] < h[b]

求，在一堆信封中，最多能有多少个个信封可以套在一起？

解题思路

基于生活经验的朴素思路：

既然想要套更多的信封，那么先找最小的信封出来，准没错，找出宽高最小的信封a。

然后，再选一个 “最贴近a，又比a大” 的信封。重复该步骤，积累的信封个数就是题目所求了。

写代码时，排序，按宽优先升序排序,这样，a的下一个信封，就是“最贴近a，又比a大”的信封。

结果发现，像这样（排序后）的用例是没问题的。

[1,1], [2,3], [3,4]

但是，如下的用例就出现问题了

[1,7], [2,3], [3,4]

按照写法，我们会直接选择，[1,7]，之后的信封都不能继续套入，故结果为1，而更优的选择为选后两个信封，结果为2。

问题出在哪里了呢？

我们平白无故的添加一个比较条件，按宽优先排序，比如 [1,7] < [2,3]，我宽小于你，可我高大于你，凭啥我就低你一等呢？

原来，信封[1,7]，[2,3] 之间并没有所谓的大小关系，故我们朴素思路问题出现在了这里。

感慨，生活中很多时候，自己遇到比较复杂的问题时，会想当然的添加某些条件，使其合理化。比如，为啥自己工作那么久还在小公司颠簸，安慰自己说，进大厂的人 毕竟是少数，自己是野鸡大学的嘛。而这问题出现在哪呢？

回归本题，我们添加这个“按宽优先升序”条件后，虽然不能直接用朴素的思路来解决，但似乎有点用到，如，比信封i大的信封一定在其后面了，故基于此继续思考。

面对排序好的信封 envelopes，如何选择第一封信封呢？如

[1,7], [2,3], [3,4]

我们选择了[2,3]作为第一个信封，因为选择它之后，我们可以再套一个[3,4]，而其它两个信封着都没有这样的“额外好处”，或者说其他两信封给的“额外好处”为0，可以说， 我们是根据它们给的“好处值”的大小来做出选择的，我们定义每个信封的好处值goods[i]为，选择它之后最终可以有多少个信封。 如以上用例的好处值分别为：

1, 2, 1

那么我们问题所求 ans = maxOf(goods[0], goods[1]… goods[n-1])

我们试图分别求每个goods[i]值，让人难以理解的一点是，求goods[i]似乎是跟求原问题是类似的…

发现求goods[i] 依赖后面信封的好处值和大小，而求最后一个信封的好处值是最容易的，必须等于1.

goods[n-1] = 1

goods[k] = 在后面的信封中，选择比envelopes[k]大的集合中选择好处值最大的 good+1

啊，发现描述起来好难~

代码：

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 {
    public int maxEnvelopes(int[][] envelopes) {
        if (envelopes.length == 0) {
            return 0;
        }
        int n = envelopes.length;
        // 将信封按宽优先升序排序
        Arrays.sort(envelopes, (o1, o2) -> o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]) : Integer.compare(o1[0], o2[0]));
        
        int[] goods = new int[n];
        goods[n - 1] = 1;
        int res = 1;
        for (int i = n - 2; i >= 0; i--) {
            int good = 0;
            for (int j = n - 1; j > i; j--) {
                if (envelopes[j][0] > envelopes[i][0]) {   // 比较宽
                    if (envelopes[j][1] > envelopes[i][1]) {    // 比较高
                        good = Math.max(good, goods[j]);
                    }
                } else {   // 寻找比信封i大的信封，信封j不可能时，前面的信封宽更小，
                    break;
                }
            }
            goods[i] = good + 1;
            res = Math.max(res, good);
        }
        return res;
    }
}