单调栈

// ⚠️ 始终用 ArrayDeque 替代 Stack（性能差3-5倍）
Deque<Integer> stack = new ArrayDeque<>(); 
int[] res = new int[nums.length];
Arrays.fill(res, -1); // 默认无更大元素for (int i = 0; i < nums.length; i++) {// 核心：当前元素 > 栈顶 → 栈顶的"下一个更大"就是nums[i]while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {int idx = stack.pop();res[idx] = nums[i]; // 或 i - idx（距离）}stack.push(i); // 存索引！非值！
}
⚠️ 三大铁律（违反必错）
栈中存索引，不存值：索引可反推值、位置、距离；值丢失位置信息。
比较用 > / <，不用 >= / <=：等号处理决定“相等元素是否视为更大”，需根据题意调整（见下文#84题）。
循环结束后栈非空 ≠ 错误：剩余元素确实没有“下一个更大”，已由初始化 -1 覆盖。
public int[] nextGreaterElement(int[] nums1, int[] nums2) {Map<Integer, Integer> map = new HashMap<>();Deque<Integer> stack = new ArrayDeque<>();// 预处理nums2：建立"值→下一个更大值"映射for (int num : nums2) {while (!stack.isEmpty() && num > stack.peek()) {map.put(stack.pop(), num);}stack.push(num); // 此题可存值（因nums1查询用值）}int[] res = new int[nums1.length];for (int i = 0; i < nums1.length; i++) {res[i] = map.getOrDefault(nums1[i], -1);}return res;
}

　　BFS

public int bfs(int[][] grid, int startR, int startC) {int rows = grid.length, cols = grid[0].length;boolean[][] visited = new boolean[rows][cols];Deque<int[]> queue = new ArrayDeque<>(); // ⚠️ 不用LinkedListqueue.offer(new int[]{startR, startC});visited[startR][startC] = true; // ⚠️ 入队时标记！非出队时！int steps = 0;while (!queue.isEmpty()) {int size = queue.size(); // 当前层节点数for (int i = 0; i < size; i++) {int[] cur = queue.poll();if (/* 到达目标 */) return steps;for (int[] dir : DIRS) {int nr = cur[0] + dir[0], nc = cur[1] + dir[1];if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc] && grid[nr][nc] == 0) {visited[nr][nc] = true; // ⚠️ 入队前标记防重复入队queue.offer(new int[]{nr, nc});}}}steps++; // 处理完一层}return -1; // 不可达
}

　　

步骤1：状态定义（最关键）

• 问自己：dp[i] 或 dp[i][j] 代表什么具体含义？
• 中等题常见模式：
  • dp[i]：以第i个元素结尾/开头的最优解
  • dp[i][j]：前i个物品容量为j / s1前i字符与s2前j字符
  • dp[i][mask]：状态压缩（中等题较少见）
• 检验标准：能否用一句话清晰描述？若模糊则重新定义。

步骤2：转移方程

• 思考路径：当前状态如何由更小规模子问题推导？
• 中等题特征：通常只有1-2个来源，不会出现复杂枚举。
• 边界处理：显式初始化base case，避免循环内特判。

步骤3：遍历顺序

• 铁律：计算dp[i]时，其所依赖的状态必须已计算。
• 快速判断：
  • 依赖i-1 → 正序
  • 依赖i+1 → 倒序
  • 二维依赖左上 → 正序行列
  • 二维依赖左+上 → 正序行列（可优化）
  • 一维背包依赖上一行 → 倒序（防覆盖）

步骤4：空间优化（可选但推荐）

• 滚动数组：二维→一维，注意遍历方向
• 变量替代：一维→O(1)，仅当只依赖前1-2个状态时
• 面试策略：先写未优化版确保正确，再口述优化思路；若时间充裕再实现。

• // 【基础版】O(N²) - 面试首选展示DP思维
  public int lengthOfLIS(int[] nums) {int n = nums.length;int[] dp = new int[n]; // dp[i]: 以nums[i]结尾的LIS长度Arrays.fill(dp, 1);   // base case: 单个元素长度为1

  // 【二维版】清晰展示状态转移
  public int coinChange2D(int[] coins, int amount) {int n = coins.length;int[][] dp = new int[n + 1][amount + 1];// base case: 0元需0枚；其他初始化为极大值for (int j = 1; j <= amount; j++) dp[0][j] = amount + 1;for (int i = 1; i <= n; i++) {for (int j = 0; j <= amount; j++) {dp[i][j] = dp[i-1][j]; // 不选第i种硬币if (j >= coins[i-1]) {dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i-1]] + 1); // 选（可重复）}}}return dp[n][amount] > amount ? -1 : dp[n][amount];
  }// 【一维优化版】生产级写法
  public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;for (int coin : coins) {for (int j = coin; j <= amount; j++) { // ⚠️ 正序！完全背包特征dp[j] = Math.min(dp[j], dp[j - coin] + 1);}}return dp[amount] > amount ? -1 : dp[amount];
  }
  

  　　

  int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; } // 【进阶版】O(N log N) - 贪心+二分，体现算法深度 public int lengthOfLISOptimized(int[] nums) { List<Integer> tails = new ArrayList<>(); // tails[k]: 长度为k+1的LIS最小末尾 for (int num : nums) { int pos = Collections.binarySearch(tails, num); if (pos < 0) pos = -(pos + 1); // 插入位置 if (pos == tails.size()) { tails.add(num); // 扩展最长长度 } else { tails.set(pos, num); // 替换使末尾更小 } } return tails.size(); }