题解 | #最长递增子序列#

单调栈，并记录arr中各个元素对应的最长递增子序列的长度，用于寻找对应的最长递增子序列

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> ans;
        int n = arr.size();
        if (n == 0) return ans;

        vector<int> dp(n, 1);

        for (int i = 0; i < n; ++i) {
            if (ans.empty() || (i > 0 && arr[i] > ans.back())) {
                ans.push_back(arr[i]);
                dp[i] = ans.size(); // 当前位置的最大长度 
            }
            else {
                int pos = lower_bound(ans.begin(), ans.end(), arr[i]) - ans.begin(); // 寻找第一个大于等于arr[1]的元素位置
                ans[pos] = arr[i];  // 替换为当前值arr[i]
                dp[i] = pos + 1;  // 当前位置的最大长度 
            }
        }
        // 第二步：填充最长递增子序列
        for (int i = n-1, j = ans.size(); j > 0; --i) {
            if (dp[i] == j) {   // 当前位置的长度 == 在ans中的位置
                ans[--j] = arr[i];
            }
        }
        return ans;
    }
};