网站建设 常用字体dnsprefetch wordpress

网站建设 常用字体,dnsprefetch wordpress,集团网站网页模板,可以在手机建网站的https://leetcode.cn/problems/longest-increasing-subsequence/ 快手一面手撕算法 我们这篇文章的解法#xff0c;结合了 贪心思想 二分查找#xff0c;非常精妙 算法解析 #x1f3af; 问题回顾 给定一个整数数组 nums#xff0c;找出其中严格递增的子序列的最大长度…https://leetcode.cn/problems/longest-increasing-subsequence/ 快手一面手撕算法我们这篇文章的解法结合了贪心思想 二分查找非常精妙算法解析 问题回顾给定一个整数数组nums找出其中严格递增的子序列的最大长度。例如nums [10,9,2,5,3,7,101,18]最长递增子序列可以是[2,3,7,18]或[2,3,7,101]长度为4。注意子序列 ≠ 子数组不要求连续。 核心思想“用更小的尾巴争取更长的未来”我们不关心具体的 LIS 是什么只关心它的长度。于是我们可以维护一个数组tails其含义是tails[i]表示所有长度为i1的递增子序列中末尾元素的最小值。✅ 为什么维护“最小末尾”末尾越小后面就越容易接上更大的数从而延长子序列。这是一种贪心策略在保证长度的前提下让结尾尽可能小。 举个例子手动模拟输入nums [10, 9, 2, 5, 3, 7, 101, 18]我们逐个处理每个数字x并更新tailsxtails处理前操作tails处理后说明10[]空直接 append[10]长度1的LIS最小末尾是109[10]找第一个 ≥9 的位置 → index0[9]用9替换10更小的末尾更好2[9]找 ≥2 → index0[2]继续优化长度1的末尾5[2]5 2 → 可延长[2,5]现在有长度2的LIS末尾53[2,5]找 ≥3 → index15≥3[2,3]长度2的末尾从5→3更优7[2,3]7 3 → 延长[2,3,7]出现长度3101[2,3,7]1017 → 延长[2,3,7,101]长度418[2,3,7,101]找 ≥18 → index3101≥18[2,3,7,18]长度4的末尾优化为18✅ 最终len(tails) 4就是答案 注意tails本身不一定是真实的 LIS比如中间过程[2,3,7,18]是真的但有些情况不是但它长度一定等于 LIS 长度 算法步骤详解from bisect import bisect_left def lengthOfLIS(self, nums: List[int]) - int: tails [] # 初始化空数组 for x in nums: # 在 tails 中找第一个 x 的位置 pos bisect_left(tails, x) if pos len(tails): # x 比所有 tails 元素都大 → 可以延长 LIS tails.append(x) else: # 替换 tails[pos] 为 x使该长度的末尾更小 tails[pos] x return len(tails)关键点解析1.bisect_left(tails, x)的作用因为tails始终保持严格递增证明见下文所以可以用二分查找。bisect_left返回第一个≥ x的索引。2.为什么tails是递增的假设存在i j但tails[i] ≥ tails[j]。那么长度为j1的 LIS 末尾是tails[j]而tails[j] ≤ tails[i]。但我们完全可以从这个长度为j1的序列中取前i1个元素得到一个长度为i1、末尾 ≤tails[j] ≤ tails[i]的序列 —— 这与tails[i]是“长度 i1 的最小末尾”矛盾。✅ 所以tails必然严格递增正因为tails有序才能用bisect_left3.替换操作不会影响已有的 LIS 长度替换只是优化未来可能性不改变当前最大长度。例如[2,5]→[2,3]长度仍是2但后续遇到4时就能组成[2,3,4]而[2,5]就不行。⏱️ 复杂度分析时间复杂度遍历n个元素 → O(n)每次二分查找 → O(log L)L 是当前 LIS 长度≤ n总计O(n log n)空间复杂度tails最多存 n 个元素 →O(n)✅ 这是目前已知的 LIS 问题最优解法仅求长度时。❗ 常见误区澄清误区正确理解“tails就是最长递增子序列”❌ 不一定它只保证长度正确内容可能不是真实子序列“只能用于严格递增”✅ 是的本题是严格递增。若允许非严格≤需改用bisect_right“不能还原具体 LIS”✅ 正确此方法只求长度。若要输出具体序列需用 O(n²) DP 回溯 测试用例验证nums [0,1,0,3,2,3] → tails 变化 0: [0] 1: [0,1] 0: [0,1] → 替换0? 不bisect_left([0,1], 0)0 → tails[0]0不变 3: [0,1,3] 2: [0,1,2] 3: [0,1,2,3] → 长度4 ✅✅ 总结一句话记住这个算法“维护一个递增的‘尾巴数组’每次用新数字要么延长它要么优化某个位置的尾巴使其更小——这样未来的增长空间更大。”这既是贪心局部最优又借助二分高效查找是算法设计中的经典范式。跟着例子学算法输入nums [10, 9, 2, 5, 3, 7, 101, 18]from bisect import bisect_left from typing import List class Solution: def lengthOfLIS(self, nums: List[int]) - int: tails [] # tails[i] 表示长度为 i1 的递增子序列的最小末尾 for x in nums: pos bisect_left(tails, x) # 关键找插入位置 if pos len(tails): tails.append(x) # 能延长 LIS else: tails[pos] x # 优化某个长度的末尾 return len(tails)下面我们逐行、逐元素地解释代码在每一步做了什么并对应到你表格中的状态变化。 初始状态tails []tails为空表示还没有任何递增子序列。 第1步x 10pos bisect_left(tails, 10) # tails[], 所以 pos 0 if pos len(tails): # 0 0 → True tails.append(10) # tails [10]✅作用第一个数直接作为长度为1的LIS的末尾。tails [10] 第2步x 9pos bisect_left([10], 9) # 在 [10] 中找 ≥9 的位置 → index0 if 0 len([10])? → 0 1? → False else: tails[0] 9 # tails [9]✅作用9 比 10 小不能延长因为 9 10但我们要严格递增且当前最长只有1但可以用 9替代长度为1的LIS的末尾使其更小为未来留空间。tails [9] 第3步x 2pos bisect_left([9], 2) # 2 9 → pos 0 0 ! 1 → 进入 else tails[0] 2 # tails [2]✅作用继续优化“长度为1”的LIS末尾从9降到2更小更好tails [2] 第4步x 5pos bisect_left([2], 5) # 5 2 → 所有元素 5 → pos len(tails) 1 if 1 1 → True tails.append(5) # tails [2, 5]✅作用5 比当前所有末尾都大比2大说明可以接在[2]后面形成长度为2的递增子序列[2,5]。tails [2, 5] 第5步x 3pos bisect_left([2,5], 3) # # 2 3 → 继续5 ≥ 3 → 停在 index1 pos 1 len(tails)2 → 1 ! 2 → else tails[1] 3 # tails [2, 3]✅作用3 不能延长到长度3因为 3 5但它可以替代长度为2的LIS的末尾原来长度2的末尾是5如[2,5]现在可以用[2,3]末尾更小以后遇到4就能接上tails [2, 3] 第6步x 7pos bisect_left([2,3], 7) # 7 3 → pos 2 len(tails)2 → 2 2 → True tails.append(7) # tails [2, 3, 7]✅作用7 比所有末尾都大可以接在[2,3]后形成长度为3的LIS[2,3,7]。tails [2, 3, 7] 第7步x 101pos bisect_left([2,3,7], 101) # 101 7 → pos 3 3 len(tails)3 → True tails.append(101) # tails [2, 3, 7, 101]✅作用继续延长得到长度为4的LIS。tails [2, 3, 7, 101] 第8步x 18pos bisect_left([2,3,7,101], 18) # 218, 318, 718, 101≥18 → pos 3 len(tails)4 → 3 ! 4 → else tails[3] 18 # tails [2, 3, 7, 18]✅作用18 不能形成长度5因为 18 101但前面最大末尾是101而18比它小但它可以优化长度为4的LIS的末尾原来是[2,3,7,101]现在可以是[2,3,7,18]末尾更小如果后面有19、20就能继续延长tails [2, 3, 7, 18] 最终结果return len(tails) # 4✅ 返回4正是 LIS 的长度。 核心代码逻辑总结代码行作用pos bisect_left(tails, x)在已有的“最优末尾”中找到第一个 ≥ x 的位置if pos len(tails):说明 x 比所有末尾都大 → 可以延长LIStails.append(x)新增一个更长的长度else: tails[pos] x用 x替换某个长度的末尾使其更小贪心优化 为什么这样是对的tails始终保持严格递增可数学归纳法证明每次操作都不减少 LIS 长度只可能增加或优化最终len(tails)就是最长可能的长度✅ 总结一句话代码通过维护一个“各长度下最小末尾”的有序数组tails利用二分查找高效决定是延长序列还是优化已有长度的结尾——从而在 O(n log n) 时间内求出 LIS 长度。