Share my 8-line O(nlgn) java code with comments (in mandarin)


  • 2
    M
    /*
        O(nlgn):
        定义 -- cap[i]为长度为i+1的上升子序列的末尾元素的最小可能值.
        中心思想 -- 对长度为m的上升子序列, 要找的是它的“最紧(tightest)”版本, 这样它扩充为长度为m+1的序列的可能性才最大.
        we claim -- cap[i]是(严格)单调递增的.
        proof of the claim -- 假设cap[i]序列不是严格单调递增的, 则在某k处有cap[k] > cap[k+1]
        (cap[k]==cap[k+1]不可能出现, 对于相等的cap, 忽略, 因为它不能让这个子序列变得更紧). 
        由于cap[k+1]的存在, cap[k]显然不是长度为k+1的上升序列的末尾元素的最小可能值, 与定义矛盾.
        what we need -- cap[i]序列的最终长度
    */
    public class Solution {
        public int lengthOfLIS(int[] nums) {
            if (nums==null || nums.length==0) { return 0; }
            List<Integer> cap = new ArrayList<>();
            for (int num: nums) {
                if (cap.isEmpty() || num>cap.get(cap.size()-1)) { cap.add(num); continue; }
                int res = Collections.binarySearch(cap, num);
                if (res < 0) { cap.set(-1-res, num); }
            }
            return cap.size();
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.