题解 | #递减种子序列#

知识点

动态规划，数据结构优化

思路

此题数据范围较小，可以采用O(NxN)的做法，即每一次遍历到seeds[i]，都往回寻找最大的DP[1~i],其中dp[x]表示以第x位结尾的最大单调递减子序列长度，此方法较为简单。

本题中，笔者采用数据结构优化，将时间复杂度降低至O（NlogN）。思路为：将seeds[1]储存进一个栈s中，每次读取seeds[i]，将它与栈顶的值作比较，若seed[i]<s.top(),则入栈，否则在栈中找到一个大于或等于seeds[i]的第一个数，并将其替换为seeds[i]，以此维护继续延长为单调递减子序列的“潜力”。

栈中的数不一定是最终的单调递减子序列，但是栈的长度即为子序列长度。

本题中，为了方便查找和替换操作，考虑到栈的单调性，可以使用VECTOR模拟，并使用lower_bound函数进行二分查找

代码c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param seeds int整型vector 
     * @return int整型
     */
    int lengthOfLIS(vector<int>& seeds) {
        vector<int>s;
        s.push_back(seeds[0]);
        int cnt=0;
        for(int i=1;i<seeds.size();i++)
        {
            if(seeds[i]<s[cnt])
            {
                s.push_back(seeds[i]);
                cnt++;
            }
            else {
                auto temp=lower_bound(s.begin(),s.end(),seeds[i],greater<int>());
                *temp=seeds[i];
            }
            
        }
        return s.size();
    }
};