面试题库 › 游戏开发 › 最长递增子序列与 STL 容器对比

最长递增子序列与 STL 容器对比

难度 ★★☆在 1 场真实面经中被问到 方向:游戏开发考点:动态规划

哪些公司问过

游戏公司合集1

常见岗位:游戏客户端

答案要点

  1. DP:dp[i] = max(dp[j]) + 1(j < i 且 arr[j] < arr[i]),O(n²)
  2. 贪心 + 二分:tails 存各长度最小末尾,O(n log n)
  3. vector:连续内存、随机访问 O(1)、中间插入 O(n)、扩容使迭代器失效
  4. list:双向链表,已知位置增删 O(1),无随机访问
  5. map:通常为红黑树,有序,增删查 O(log n)

易错点

面试官常见追问

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

相关面试题