题解 | #最长上升子序列(三)#

解题思路：

创建一个dp的二维数组（n*3）

创建一个由优先队列（最小堆）组成的数组v

样例：

dp[i][0]: 2 1 5 3 6 4 8 9 7

dp[i][1]: 1 1 2 2 3 3 4 5 4

dp[i][2]: 0 0 1 1 3 3 4 8 4

dp[i][0]:arr[i]

dp[i][1]:到第i个元素时，包含该元素的最长的子序列长度

dp[i][2]:到第i个元素时，包含该元素的最长的子序列中，倒数第二个元素

dp[i][1]的计算方法：

获得当前元素arr[i]

从大到小地遍历现有的优先队列数组，找到第一个合适的(当前元素大于该优先队列的最小值)优先队列；

找到合适的优先队列等于知道了加上当前元素，子序列的最大长度k，

然后将该元素插入到v[k-1]中(v[k-1]为以所有子序列中，第k个元素的最小堆，

如样例中的最小堆有（2，1），（5，3），（6，4），（8，7），（9）

)

dp[i][2]的计算方法：

计算dp[i][1]时，找到的合适的优先队列的堆顶元素就是dp[i][2]

得到dp数组后，

先找到dp二维数组中，dp[i][1]为最大并且dp[i][0]最小的一维数组，

将目标元素dp[i][0]存放在最终答案 answer中

并且将i的位置记为position，

将dp[i][1]（长度）记为maxn ,

将dp[i][2]（子序列中前一个元素）记为target

然后从i向v.begin()遍历找到长度为maxn-1并且当前元素为target的元素

将当前元素存放进answer中，并且更新maxn和target

最后反转answer得到最终答案

#include <algorithm>
#include <climits>
#include <functional>
#include <queue>
#include <utility>
class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        vector<int> answer;
        if(arr.size() == 0){
            return answer;
        }
        vector<priority_queue<int,vector<int>, greater<int> > > vp; //用优先队列保存相等的子序列
        priority_queue<int,vector<int>, greater<int> > first;
        vector<vector<int> > dp;                                    //第一个int为arr里的元素
                                                                    //第二个int为包括该元素的最长子序列长度
        first.push(arr[0]);
        vp.push_back(first);
        vector<int> t = {arr[0],1,0};
        dp.push_back(t);
        for(int i = 1 ; i < arr.size() ; i++){                      //遍历arr中的每一个元素
            int j;
            int pre;
            for(j = vp.size()-1; j >= 0; j--){                      //从大到小遍历每个优先队列，每个优先队列的队头都是最小值
                                                                    //找到的第一个值一定是最大长度队列中的最小值
                if(arr[i]>vp[j].top()){
                    pre = vp[j].top();
                    if(j == vp.size()-1){                           //如果第一个队列就是目标队列，说明遇到新的最大长度
                        priority_queue<int,vector<int>, greater<int> > now;
                        now.push(arr[i]);
                        vp.push_back(now);
                        break;
                    }else{                                          //否则将该元素插入到已有队列中
                        vp[j+1].push(arr[i]);
                        break;
                    }    
                }
            }
            vector<int> t;
            if(j != -1){                                            //如果找到了目标队列，则记录该元素的最长子序列长度
                t = {arr[i],j+2,pre};                       
                dp.push_back(t);   
            }else{                                                  //没找到，说明其比之前所有元素都小，其子序列长度为1
                t = {arr[i],1,0};
                dp.push_back(t);
                vp[0].push(arr[i]);
            }
        }
        int maxn = 0;                                               //长度
        int now = INT_MAX;                                          //相同长度下，元素的最小值
        int target;                                                 //前一个目标元素
        int ii;                                                     //目标元素的下标
        for(int i = dp.size()-1 ; i >=0 ; i--){                     //先找到最大长度下的最小值及其下标
            if(maxn == dp[i][1] && now > dp[i][0]){
                now = dp[i][0];
                target = dp[i][2];
                ii = i;
            }
            if(maxn < dp[i][1]){
                maxn = dp[i][1];
                now = dp[i][0];
                target = dp[i][2];
                ii = i;
            }
        }
        answer.push_back(now);
        now  = INT_MAX;
        maxn--;
        for(int j = ii ; j >=0 ; j--){                              //找下一个目标元素
            if(dp[j][1] == maxn && dp[j][0] == target){
                answer.push_back(target);
                target = dp[j][2];
                maxn--;
            }
        }
        reverse(answer.begin(), answer.end());
        return answer;


    }
};