面试题库 › C++ / 后端 › 字典序最小的最长递增子序列

字典序最小的最长递增子序列

难度 ★★★在 1 场真实面经中被问到 方向:C++ / 后端考点:动态规划

哪些公司问过

字节跳动1

常见岗位:后端开发

答案要点

  1. tails 数组 + 二分,O(n log n) 求每个位置结尾的 LIS 长度 len[i]
  2. 从右往左扫描,len[i] 等于当前所需长度就选入并将长度减一
  3. len 相同的位置中,越靠右的值不会更大
  4. 倒序选择保证每一位取到最小可能值,从而字典序最小
  5. 总时间 O(n log n),空间 O(n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题