- 正确答案：最长递增子序列（LIS）的常见改版包括：① 最长严格递增子序列（经典LIS）；② 最长非递减子序列（允许相等）；③ 最长递增子序列的个数；④ 输出任意一个LIS（或所有LIS）；⑤ 带位置约束的LIS（如必须包含第i个元素、必须以第i个元素结尾、子序列索引下标本身也需递增且间隔≥k等）；⑥ 二维LIS（如按x排序后对y求LIS，用于解决“俄罗斯套娃信封”问题）；⑦ 在线LIS（数据流中动态维护LIS长度）；⑧ LIS + 权重最大和（即最长递增子序列中元素权重之和最大，称为“最大权递增子序列”，MWIS）。其中最常考、最具代表性的改版是：**求最长递增子序列的长度（O(n log n)解法）** 和 **求以每个位置结尾的LIS长度（DP+二分优化）**，以及 **求LIS的方案数（需结合DP与计数）**。 - 解答思路：面试官说“手撕最长递增子序列的改版”，通常隐含考察候选人是否真正理解LIS的两种解法本质（O(n²) DP vs O(n log n) 贪心+二分），能否识别问题变形，并灵活迁移。典型解题路径如下：第一步：确认问题定义——是求长度？方案数？具体序列？是否允许重复？是否带权重？是否强制结尾于某位置？第二步：根据约束选择模型——若仅求长度且n较大（如10⁵），必须用O(n log n)方法；若需方案数或重建路径，则需保留更多状态（如dp[i]表示以i结尾的LIS长度，cnt[i]表示对应方案数，同时维护tail数组及对应方案映射）；第三步：构建核心数据结构——O(n log n)解法的关键是维护一个辅助数组tail，其中tail[len] = 满足“长度为len+1的递增子序列的最小末尾元素值”。该数组严格递增（可二分），其长度即为LIS长度。注意：tail不存真实子序列，仅用于长度计算和状态更新；第四步：若需方案数，需额外处理“相同tail值的多重转移”——当nums[i] == tail[pos]时，前面所有能转移到该pos的j（即dp[j] == pos 且 nums[j] < nums[i]）都要贡献方案数，此时需离线按值排序+树状数组/线段树优化，或采用“按dp值分组+单调栈+前缀和”技巧；第五步：验证边界——空数组、单元素、全等、严格降序等case。 - 深度知识讲解： 1. **底层数据结构原理**：O(n log n) LIS本质是利用Dilworth定理的对偶思想——将序列看作偏序集（i len(tail): tail.append(nums[i]) else: tail[dp[i]-1] = min(tail[dp[i]-1], nums[i]) // Group by dp value if dp[i] not in dp_groups: dp_groups[dp[i]] = [] dp_groups[dp[i]].append( (nums[i], cnt[i]) ) max_len = len(tail) total_cnt = sum(cnt[i] for i in range(n) if dp[i] == max_len) return max_len, total_cnt ``` - 扩展知识： - “俄罗斯套娃信封”问题：先按w升序、h降序排序（避免w相同导致重复计数），再对h数组求LIS——此技巧本质是将二维偏序转化为一维LIS，关键在于第二维降序以消除同一w下的非法转移。 - LIS与 patience sorting（纸牌游戏排序）等价：把每个数当作一张牌，按规则放到最左边能放的堆顶（堆顶递减），堆数即LIS长度。该模型直观解释了tail数组的物理意义。 - 若数组元素为区间（如[start, end]），定义递增为end_i < start_j，则问题转为区间图上的最长路径，可用贪心+堆（按start排序，维护最小end堆）解决，时间复杂度O(n log n)。 - 在分布式系统中，“最长递增子序列”被用于检测事件因果序（happens-before relation），此时需考虑网络延迟和时钟漂移，演变为“近似LIS”问题，引入ε-approximation算法。

美团推荐算法二面-日常实习

全站热榜

创作者周榜