讨论/建议反馈/【错误反馈】300. 最长上升子序列/
【错误反馈】300. 最长上升子序列

解题思路

本代码无法通过判例
[11,12,13,14,15,16,1,2,3,4,1,5,6,7,1,8]
但官网提交正确

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // 辅助空间 在计算过程中保持严格单增
        // tail[i] = 长度为i的上升子序列的最小末尾 
        vector<int> tail(nums.size() + 1, INT_MIN);
        int max_length = 0; // 已知最长上升子序列长度

        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > tail[max_length]){
                // 如果num[i]严格大于所有tail,则追加
                // 在计算过程中保持严格单增
                // 即最长上升子序列+1,并以num[i]结尾
                tail[++max_length] = nums[i];
            }else{
                // 使用二分搜索定位第一个大于num[i]的tail
                int l = 0, r = max_length;
                int mid = 0;
                while(l < r){
                    mid = (l + r) / 2;
                    if(tail[mid] == nums[i]){
                        // 当tail中含有相等num[i]的元素时不能进行替换操作
                        mid = -1;
                        break;
                    }else if(tail[mid] < nums[i]){
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }
                if(mid != -1){
                    // 替换(缩小)第一个大于num[i]的上升子序列的最小末尾
                    // 此处即使不进行if-else判断也可以通过LeetCode
                    // 但是这样并没有保证每次换掉的是第一个更大的
                    // tail序列将会不同,但长度不变
                    // 可能的猜想:
                    // 1. 算法可以优化,可能不需要保存所有之前更短的状态
                    // 2. LeetCode判例不足
                    // if(tail[l] > nums[i])
                        tail[l] = nums[i];
                    // else
                    //     tail[l+1] = nums[i];
                }
            }
            // for(int q = 1; q <= max_length; q++){
            //     cout<<tail[q]<<" ";
            // }
            // cout<<endl;
        }

        // 最终tail的长度即为最长上升子序列长度
        return max_length;
    }
};
展开讨论
共 2 个讨论

楼主说的是对的,的确是用例太少。

还请「力扣」@LeetCode 把用例加一下,辛苦了。

或者楼主可以按照帖子 力扣(LeetCode)题目 / 题解快速反馈通道开始试行! 给官方提交一个 issue。

1

感谢反馈,我们创建了一个 Github 仓库 用于收集大家在本站学习过程中遇到的题目和题解BUG,您可以把遇到的问题直接按 issue 模板提交(可以使用中文),我们的开发同学会尽可能快的回复并修复。