用栈实现最长递增子序列

下面是使用栈实现最长递增子序列的代码：

int findLongestIncreasingSubsequence(vector<int>& nums) {
    stack<int> s;
    for (int num : nums) {
        if (s.empty() || num > s.top()) {
            s.push(num);
        } else {
            auto it = lower_bound(nums.begin(), nums.end(), num);
            *it = num;
        }
    }
    return s.size();
}

该算法与前面提到的算法很类似，唯一的区别在于当发现一个数小于等于栈顶元素时，不直接将其替换掉，而是在原数组中找到第一个大于等于这个数的位置，将其替换为这个数。这样做的目的是为了保证栈中的元素是一个递增的序列。

该算法的时间复杂度为 $O(n \log n)$，其中 $n$ 是数组的长度，因为在查找第一个大于等于某个数的位置时使用了二分查找，而二分查找的时间复杂度是 $O(\log n)$。