前端算法不必追求竞赛难度，核心是拆问题、分析复杂度、写出稳定代码。本文整理常用数据结构与算法思想。

数据结构

数组与链表

数组支持随机访问，按索引读取是 O(1)，但中间插入删除通常是 O(n)。链表插入删除节点方便，但查找需要遍历。数组常配合双指针、滑动窗口、前缀和；链表常考反转、快慢指针、环检测、合并。

判断链表是否有环：用快慢指针。慢指针每次走一步，快指针每次走两步。如果有环，两者一定会相遇；如果快指针走到空，说明无环。

栈与队列

栈是后进先出，适合括号匹配、单调栈、函数调用、撤销操作。队列是先进先出，适合 BFS、任务调度。双端队列常用于滑动窗口最大值。

有效括号：遇到左括号入栈，遇到右括号就看栈顶是否匹配。最后栈为空才合法。关键是提前处理栈空和类型不匹配。

树与图

树题重点是递归定义：一棵树的问题通常可以拆成当前节点和左右子树。图题重点是建图、访问标记和遍历策略。无权最短路用 BFS，有权最短路才考虑 Dijkstra。

二叉树最大深度：递归返回左右子树最大深度加一；或者层序遍历，每遍历一层深度加一。

常见算法思想

DFS 与 BFS

DFS 适合路径搜索、回溯、连通块；BFS 适合层级遍历和无权最短路径。DFS 通常用递归或栈，BFS 通常用队列。

岛屿数量：遍历网格，遇到陆地就计数，并用 DFS 或 BFS 把相连陆地全部标记为已访问。时间复杂度 O(mn)。

二分查找

二分的本质是在单调性上排除一半答案。可以二分数组下标，也可以二分答案。关键是定义搜索区间、循环条件和边界收缩方式。

二分容易死循环，常见原因是边界更新没有保证区间变小，或者 mid 偏向错误。写题前先明确用闭区间 [left, right] 还是左闭右开 [left, right)。

滑动窗口

滑动窗口适合连续子数组或子串问题。右指针扩张窗口，左指针在条件不满足或需要收缩时移动。核心是维护窗口内的状态。

最长无重复子串：用哈希表记录字符最近位置，右指针遍历字符，如果字符重复且在窗口内，就移动左指针到重复字符后一位，同时更新最大长度。

动态规划与贪心

动态规划

DP 适合有重叠子问题和最优子结构的问题。步骤是定义状态、写转移方程、确定初始化、确定遍历顺序。前端常考爬楼梯、最长递增子序列、背包、路径问题。

爬楼梯：到第 n 阶只能从 n-1 或 n-2 来，所以 dp[n] = dp[n-1] + dp[n-2]。它有重叠子问题，可以用滚动变量降到 O(1) 空间。

贪心

贪心每一步选择局部最优，希望得到全局最优。它必须能证明局部选择不会破坏全局最优。常见题有区间调度、买卖股票、跳跃游戏。

贪心和 DP 的区分：如果每步局部最优能被证明导向全局最优，用贪心；如果当前选择依赖多个历史状态，通常用 DP。

复杂度表达

时间与空间复杂度

写完算法要主动说明复杂度。复杂度不是背答案，而是说明输入规模增长时运行时间和额外空间如何增长。

递归空间复杂度：除了显式数据结构，还要算调用栈。比如二叉树 DFS 最坏空间 O(n)，平衡树平均 O(log n)。

代码示例

二分查找模板

二分题要先定义搜索区间和不变量。下面是闭区间模板：

function lowerBound(nums, target) {
  let left = 0
  let right = nums.length - 1
  let answer = nums.length

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] >= target) {
      answer = mid
      right = mid - 1
    } else {
      left = mid + 1
    }
  }

  return answer
}

mid 计算建议用 left + (right - left) / 2 而非 (left + right) / 2。在 JS 里数组长度通常不会溢出，但在 Java/C++ 中可能整数溢出，前者是更通用的习惯。

LRU 缓存

LRU 要求 get/put 都是 O(1)，常用哈希表 + 双向链表。JS 的 Map 保持插入顺序，可以写一个简化版。

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.map = new Map()
  }

  get(key) {
    if (!this.map.has(key)) return -1
    const value = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, value)
    return value
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key)
    }
    this.map.set(key, value)

    if (this.map.size > this.capacity) {
      const oldestKey = this.map.keys().next().value
      this.map.delete(oldestKey)
    }
  }
}

真实工程如果需要更高控制力，会用手写双向链表节点，避免依赖语言容器特性。

单调栈

单调栈用来找下一个更大/更小元素。栈中维护一个单调序列，新元素进来时弹出不满足条件的元素。

function dailyTemperatures(temperatures) {
  const answer = new Array(temperatures.length).fill(0)
  const stack = []

  for (let i = 0; i < temperatures.length; i++) {
    while (
      stack.length &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const prev = stack.pop()
      answer[prev] = i - prev
    }
    stack.push(i)
  }

  return answer
}

动态规划：最长递增子序列

O(n²) DP 容易理解，O(n log n) 解法用贪心 + 二分维护每个长度的最小结尾。

function lengthOfLIS(nums) {
  const tails = []

  for (const num of nums) {
    let left = 0
    let right = tails.length

    while (left < right) {
      const mid = left + Math.floor((right - left) / 2)
      if (tails[mid] >= num) right = mid
      else left = mid + 1
    }

    tails[left] = num
  }

  return tails.length
}