那些過去刻诊，從未過去防楷。

題目

給定數(shù)組arr，設(shè)長度為n坏逢，輸出arr的最長遞增子序列域帐。（如果有多個答案赘被，請輸出其中字典序最小的）
輸入描述
輸出兩行是整，第一行包括一個正整數(shù)n（n<=100000）肖揣，代表數(shù)組長度。第二行包括n個整數(shù)浮入，代表數(shù)組arr(1≤arri≤1e9)龙优。
輸出描述
輸出一行。代表你求出的最長的遞增子序列事秀。

樣例1:
[輸入]
9
2 1 5 3 6 4 8 9 7
[輸出]
1 3 4 8 9
[說明]

樣例2:
[輸入]
5
1 2 8 6 4
[輸出]
1 2 4
[說明]
其最長遞增子序列有3個彤断，（1，2易迹，8）宰衙、（1，2睹欲，6）供炼、（1，2窘疮，4）其中第三個字典序最小袋哼，故答案為（1，2闸衫，4）

解題思路

看到這道題目涛贯，有種似曾相識的感覺，仔細(xì)一看才發(fā)現(xiàn)不是這回事蔚出。LeetCode上的最長遞增子序列是輸出序列長度弟翘，屬于中等medium題，而本題在此基礎(chǔ)上需要輸出序列且需要保證字典序最小骄酗，難度瞬間陡升稀余。一開始的思路就是動態(tài)規(guī)劃，確實思路沒錯酥筝，但是到輸出隊列且字典序最小時滚躯，卡點了。目前的研究是先分成兩步解決：
1.通過dp動態(tài)規(guī)劃求出最小序列長度嘿歌。
2.生成最小字典序的序列掸掏，有兩種思路，直觀地找到所有的最長遞增子序列宙帝，選擇其中字典序最小的丧凤；或者使用某種貪心的思路找到字典序最小的序列。

第一步動態(tài)規(guī)劃步脓，首先需要定義好dp愿待。
1.定義：設(shè)dp[i]表示以arr[i]結(jié)尾的最長遞增子序列浩螺，此時注意，每一個dp值并不是遞增的仍侥，比如第一個樣例1要出，2 1 5 3 6 4 8 9 7，輸出1 3 4 8 9农渊，以9結(jié)尾的比以7結(jié)尾的序列長度更長患蹂。
2.尋找子問題推導(dǎo)：對于所有可與arr[i]組成上升序列的子序列上一個元素假設(shè)為arr[x]，x < i砸紊，需要滿足條件：arr[x] < arr[i]（嚴(yán)格遞增）传于，即需要枚舉序列，對所有滿足arr[x] < arr[i]的元素選擇一個最大的dp[x]醉顽，轉(zhuǎn)移方程：

dp[i] = max(dp[x]) + 1,  x < i且 arr[x] < arr[i]沼溜。

3.第一步代碼如下：

public int lengthOfLIS(int[] nums) {
        if(nums.length == 1) return 1;
        //dp[i]表示以 nums[i]結(jié)尾的最長子序列(包含nums[i])長度
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxLen = 1;
        for(int i = 1; i < nums.length; i ++) {
            //元素相等可以跳過
            if(nums[i] == nums[i -1]) dp[i] = dp[i-1];
            else{
                int maxPre = 0;
                for(int j = 0; j < i; j ++) {
                    if(nums[j] < nums[i]){//只看小于num[i]的元素
                        //找到前面這些元素結(jié)尾的最大子序列長度
                        maxPre = Math.max(dp[j],maxPre);
                    }
                }
                dp[i] = maxPre + 1; //dp[i]即為最大值加一
            }
            //記錄中間最大值記錄，后面可能會有更長的序列所以繼續(xù)遍歷
            maxLen = Math.max(maxLen,dp[i]);
        }
        return maxLen;
    }

時間復(fù)雜度O(n^2)游添，雙重循環(huán)遍歷系草，可能會超時。

另一種O(nlogn)的思路否淤，看見logn確實是二分：假如給出序列 mylist=[1悄但， 3， 5石抡， 6檐嚣， 7， 2啰扛， 5嚎京， 7， 9隐解， 10]鞍帝，找最長序列的時候，看到1, 3, 5, 6, 7遞增煞茫，長度len1=5帕涌，可能這個就是目標(biāo)序列，記為答案一续徽。 但是遇到2(mylist[5])時蚓曼，有沒有可能從1, 2, ... (mylist[0], mylist[5]...)會找到一個新的子序列， 且比之前找的序列1, 3, 5, 6, 7更長钦扭？記為答案二纫版。驗證答案二，看2以后的數(shù)字是否能找到新的遞增序列客情。有兩種結(jié)果其弊，新的答案比第一次的答案短癞己， 保留答案一； 新的答案比第一次的答案長梭伐， 用新的答案痹雅。 所以記錄 1）新的答案上一個數(shù)字，繼續(xù)往下找 2）若遍歷結(jié)束了新的答案不夠長籽御，保留答案一练慕。使用一個隊列惰匙，每次更新最長子序列時技掏，把子序列末尾最大值也就是arr[i]，替換隊列中第一個大于arr[i]的位置项鬼，若沒找到則直接放在隊尾哑梳，隊列的長度即為LIS。
解釋：當(dāng)找到2時绘盟，原來的[1, 3, 5, 6, 7], 3已經(jīng)不在新的答案序列了鸠真，把3替換為2，依次進行龄毡，如果新的答案比第一次答案長吠卷， 整個序列被替換，如果沒有第一個長沦零，替換的次數(shù)不夠祭隔，原來方案一里最大的數(shù)字還在末尾， 原始隊列的長度不會被替換路操，那么始終能用隊列的長度表示最長遞增子序列疾渴。代碼如下：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int len = 0;//最開始tails里面沒有保存數(shù)所以為0
        for(int num : nums) {
            int i = 0, j = len-1; // 對tails進行二分查找 閉區(qū)間查找，注意j從len-1開始
            int idx = lowerBound(tails,num,i,j);//左邊找大于等于num的第一個數(shù) 
            tails[idx] = num;// 使用num替換查找到的i位置
            if(len == idx) len++; // idx=len說明放在tails后面了len++
        }
        return len; // len即為LIS
    }
   
    //左閉右閉區(qū)間返回的是不變量l或r-1屯仗，表示>=target的左邊第一個數(shù)
    int lowerBound(int[] arr,int target, int l, int r) {
        while(l  <= r) {
            int mid = l + (r-l)/2;
            if(arr[mid] < target) l = mid+1;
            else r = mid-1;
        }
        return l;
    }
}

對二分不熟悉的小伙伴可以多學(xué)習(xí)鞏固一下相關(guān)的寫法搞坝，不管開區(qū)間閉區(qū)間寫法還是小于等于或大于等條件，都是一樣的思路魁袜，比如找大于x的第一個位置相當(dāng)于找大于等于x+1的位置（對于整數(shù)區(qū)間）桩撮，我個人習(xí)慣用閉區(qū)間。

第二步 求解字典序最小峰弹，需要利用到dp[i]記錄的以nums[i]結(jié)尾的LIS：

        // 反向遍歷店量，每次都減少遞增序列長度
        int[] res = new int[len];
        for (int i = n - 1; i >= 0; i--) {
            //從后向前依次給子序列賦值
            if (dp[i] == len) {//可能有多個dp[i]都是最長遞增子序列 為何選擇后面這個？
                res[len - 1] = nums[i];
                len -= 1;
            }
        }
        return res;

倒序遍歷時垮卓，可能有多個dp[i]都是最長遞增子序列 為何選擇后面這個垫桂？
反證：假設(shè)有dp[x] = dp[x+k] = maxLen，若nums[x] < nums[x+k]粟按，則nums[x+k]可以接在nums[x]后面組成上升序列诬滩，則dp[x+k] > dp[x]矛盾霹粥。

最終代碼如下：

class Solution {
    public int[] LIS(int[] nums) {
        int n = nums.length;
        int[] tails = new int[n];
        int[] dp = new int[n];
        int len = 0;
        for (int i = 0; i < n; i++) {
            int l = 0, r = len - 1; // 對tails進行二分查找 閉區(qū)間查找，注意j從len-1開始
            int idx = lowerBound(tails, nums[i], l, r);//左邊找大于等于num的第一個數(shù)
            tails[idx] = nums[i];// 使用num替換查找到的i位置
            if (len == idx) len++; // idx=len說明放在tails后面了len++
            dp[i] = idx + 1;
        }
        int[] res = new int[len];
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] == len) {
                res[len - 1] = nums[i];
                len -= 1;
            }
        }
        return res;
    }

    //左閉右閉區(qū)間返回的是不變量l或r-1疼鸟，表示>=target的左邊第一個數(shù)
    int lowerBound(int[] arr, int target, int l, int r) {
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return l;// 沒找到時后控，一直往右逼近，最終返回的是數(shù)組長度（r-l+1）
    }
}

思考：打印所有最長遞增子序列空镜。
2024-03-29