Longest Increasing Subsequence ⭐⭐

• 题目地址: https://leetcode-cn.com/problems/longest-increasing-subsequence
• 执行时间: 0 ms
• 内存消耗: 2.4 MB
• 通过日期: 2019-03-20 19:15

题目内容

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:

• 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
• 你算法的时间复杂度应该为 O(n²) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解法

// Author: Netcan @ https://github.com/netcan/Leetcode-Rust
// Zhihu: https://www.zhihu.com/people/netcan

impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        let mut longest = Vec::with_capacity(nums.len());

        for num in nums {
            match longest.binary_search(&num) {
                Err(pos) => {
                    if pos < longest.len() {
                        longest[pos] = num;
                    }  else  {
                        longest.push(num);
                    }
                },
                _ => {}
            }
        }

        longest.len() as i32
    }
}