题目链接：354

思路

本题的官方解答写的很不错，特别是一步步推理排序应该按照width递增、height递减的规律进行。

这道题的大致思路是：排序 + 最长递增子序列。我觉得这题的难点有：1. 怎么想到使用最长递增子序列；2. 按照什么规律排序可以简化最长递增子序列。

leetcode第300题是最长递增子序列的母题。最长递增子序列的特点在于，元素之间有一种严格的递增逻辑，整个序列具有严格的固定逻辑。反观本题（354），其实所描述的问题中元素之间也具有严格的递增逻辑，只不过从一维的升级为了二维，因此本题适合使用最长递增子序列来完成。

为了简化难度，可以先对原来的信封数组进行排序，最直观的排序方法是：width递增、width相同时height递增排序，排序好后对整个信封做最长递增子序列。但在这个过程中，由于width相同的时，即使height是递增的，后一个信封也不能装前一个信封，因此这是一个二维的最长递增子序列，在做最长递增子序列时还需要将width考虑进去。

那如果换个排序方法，按照width递增、width相同时height递减来排序。这样，当width相同时，由于height是递减的，在做最长递增子序列时width相同的信封之间不会相互影响。于是可以忽略width，直接对height做最长递增子序列就行了，这就降维成了一维的最长递增子序列。一维最长递增子序列可以使用binary search进行优化，具体的解法可以看另一篇文章：300. Longest Increasing Subsequence。

func maxEnvelopes(envelopes [][]int) int {
    // sort with increasing width and decreasing height
    sort.Slice(envelopes, func(i, j int) bool {
        a, b := envelopes[i], envelopes[j]
        return a[0] < b[0] || a[0] == b[0] && a[1] > b[1]
    })

    // do longest increasing subsequence
    // tails[i]: the end element of increasing subsequence which length is i+1
    // with tails[], we can do increasing subsequence in O(nlogn) instead of O(n^2)
    tails := make([]int, 0, len(envelopes))
    tails = append(tails, envelopes[0][1])

    for i := 1; i < len(envelopes); i++ {
        index := binarySearchBiggestSmaller(tails, envelopes[i][1])
        if index == -1 {
            // no smaller element
            tails[0] = min(tails[0], envelopes[i][1])
        } else if index == len(tails) - 1 {
            // the biggest element is smaller than current
            tails = append(tails, envelopes[i][1])
        } else {
            // update tails[index + 1]
            tails[index + 1] = min(tails[index + 1], envelopes[i][1])
        }
    }

    return len(tails)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// return index
func binarySearchBiggestSmaller(array []int, pivot int) int {
    left, right := 0, len(array) - 1
    for left < right - 1 {
        mid := left + (right - left) / 2
        if array[mid] >= pivot {
            right = mid - 1
        } else {
            left = mid
        }
    }
    if array[right] < pivot {
        return right
    }
    if array[left] < pivot {
        return left
    }
    return -1
}

时间复杂度：排序 O(nlogn)，最长递增子序列 O(nlogn)，总 O(nlogn)
空间复杂度：O(n)