[LeetCode] 354. Russian Doll Envelopes

轉自LeetCode

You are given a 2D array of integers envelopes where envelopes[i] = [wi, hi] 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.

 

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

 

Constraints:

• 1 <= envelopes.length <= 5000
• envelopes[i].length == 2
• 1 <= wi, hi <= 104

Solution

300. Longest Increasing Subsequence 的衍生題

要能把前一個信封裝進去，寬高就要比前面的大

其實也就是在找 longest increasing subsequence

但難在這次是個二維的概念，有寬和高要同時考量

因此，先對寬做排序，由小排到大，這樣歷遍的時候，就能確定大小順序

接著可以用 binary search 對高找 LIS

而排序的時候，要注意高的部分，當寬一樣大時，必須把較高的排在前面

理由是，寬已經一樣了，所以也不用再考慮寬

而把比較高的放在前面，是想讓它先被檢查

輪到下一個高比較矮的那個時，會取代掉前面的那個位置，但是整體長度沒有變

舉例 [[4,5],[4,6],[6,7],[2,3],[1,1]]

排序後會變成  [[1,1],[2,3],[4,6],[4,5],[6,7]]

歷遍到 [4,6]時，這時候紀錄的高度會是 [1,3,6]，長度是 3

檢查 [4,5] 時，會變成 [1,3,5]，長度還是 3

這是為了讓之後還有機會變更長的方式

但紀錄的高度，只有長度會是對的，裡面的值有可能會是錯的

和 300. Longest Increasing Subsequence 是一樣的邏輯

kotlin(參考解法)