题意提取
信封有两属性,宽(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 | class Solution { |