leetcode【300-最长递增子序列】思考、优化、改进

朱雀 2023-01-10 03:38 126阅读 0赞

leetcode【300-最长递增子序列】思考、优化、改进  
 声 明 ： 该 系 列 是 我 的 随 笔 ， 会 记 录 一 些 刷 题 的 感 受 ， 思 路 。 文 章 难 免 有 错 误 或 语 句 不 够 严 谨 ， 欢 迎 指 正 。 \\color\{\#FF0000\}\{声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。 \} 声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。  
 如 果 读 者 关 于 这 道 题 有 其 他 疑 问 ， 也 欢 迎 在 评 论 区 和 我 讨 论 我 会 及 时 回 复 ， 互 相 进 步 ， 谢 谢 ！ \\color\{\#FF0000\}\{如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！\} 如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！

vector<int> dp(nums.size(),1);
            for(int i=1;i<nums.size();i++)
            {    
                for(int j=0;j<i;j++)
                if(nums[i]>nums[j]&&dp[i]<=dp[j])
                    dp[i] = dp[j]+1;
            }
            int max=1;
            for(int i=1;i<nums.size();i++)
            if(max<dp[i])
            max = dp[i];
            return max;
    执行用时：340 ms, 在所有 C++ 提交中击败了38.93%的用户
    内存消耗：10 MB, 在所有 C++ 提交中击败了67.96%的用户

作为最基础的DP算法，自然无需赘述，但是为何执行用时如此之差呢，这也是不断的写这种经典问题的意图，优化自己的逻辑，养成良好的coding逻辑与风格。

究其原因上述代码中dp数组中的dp\[i\]含义是第i项的递增子序列元素个数，不但需要将i遍历一次，每一个i还需要使得j从0~i遍历一次时间复杂度O（n²）

在题解中看到了另一种：贪心+二分查找的策略，可以实现时间复杂度为O（nlogn）

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，
    因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
    
    整个算法流程为：
    设当前已求出的最长上升子序列的长度为 len（初始时为1），从前往后遍历数组 nums，在遍历到 nums[i] 时：
    如果 nums[i] > d[len] ，则直接加入到 d 数组末尾，并更新 len =len + 1
    否则，在 d 数组中二分查找，找到第一个比 nums[i] 小的数 d[k] ，并更新 d[k + 1] =nums[i]。
    以输入序列 [0, 8, 4, 12, 2][0,8,4,12,2] 为例：
    第一步插入 00，d = [0]d=[0]；
    第二步插入 88，d = [0, 8]d=[0,8]；
    第三步插入 44，d = [0, 4]d=[0,4]；
    第四步插入 1212，d = [0, 4, 12]d=[0,4,12]；
    第五步插入 22，d = [0, 2, 12]d=[0,2,12]。
    基于上面的贪心思路，我们维护一个数组 d[i] ，表示长度为 i 的最长上升子序列的
    末尾元素的最小值，用 len 记录目前最长上升子序列的长度，
    起始时 lenlen 为 1，d[1] = nums[0]。
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

上方选自leetcode官方题解，说的很清楚我就直接copy过来了，有几点需要注意  
 1. 易 证 d \[ i \] 数 组 随 着 i 的 增 加 单 调 不 减 \\color\{\#FF0000\}\{1.易证d\[i\]数组随着i的增加单调不减\} 1.易证d\[i\]数组随着i的增加单调不减  
给出一个简单的证明：假设存在i<j时有d\[i\]>\[j\]，可知存在长度为j的递增序列，不防设该递增序列为a0,a1,a2,…,aj。其中aj=d\[j\]，a0<a1<a2<…aj。必存在长度为i的递增序列a(j-i),a(j-i+1)，…,aj。由于d\[i\]>d\[j\]，故矛盾、  
 2. 数 组 d 的 长 度 即 为 最 长 上 升 子 序 列 的 长 度 \\color\{\#FF0000\}\{2.数组d的长度即为最长上升子序列的长度\} 2.数组d的长度即为最长上升子序列的长度  
 3. 为 什 么 要 证 明 单 调 不 减 呢 ？ 因 为 可 以 使 用 二 分 查 找 法 来 优 化 时 间 复 杂 度 \\color\{\#FF0000\}\{3.为什么要证明单调不减呢？因为可以使用二分查找法来优化时间复杂度\} 3.为什么要证明单调不减呢？因为可以使用二分查找法来优化时间复杂度

上一下官方代码：

class Solution { 
    public:
        int lengthOfLIS(vector<int>& nums) { 
            int len = 1, n = (int)nums.size();
            if (n == 0) { 
                return 0;
            }
            vector<int> d(n + 1, 0);
            d[len] = nums[0];
            for (int i = 1; i < n; ++i) { 
                if (nums[i] > d[len]) { 
                    d[++len] = nums[i];
                } else { 
                    int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                    while (l <= r) { 
                        int mid = (l + r) >> 1;
                        if (d[mid] < nums[i]) { 
                            pos = mid;
                            l = mid + 1;
                        } else { 
                            r = mid - 1;
                        }
                    }
                    d[pos + 1] = nums[i];
                }
            }
            return len;
        }
    };

学习之路任重道远啊~这个方法完全没有想到