巴音郭楞蒙古自治州网站建设_网站建设公司_关键词排名_seo优化

在算法刷题中，“思路的迭代”往往比 “写出代码” 更有价值 —— 从暴力遍历到贪心、从递归到迭代、从局部最优到全局最优，每一步优化都体现了算法思维的进阶。本文以 LeetCode 中 3 道经典题（岛屿面积、反转链表、分发糖果）为例，拆解其解题思路的 “深度” 所在。

695. 岛屿的最大面积：DFS 的 “淹没式” 遍历思维

问题本质

在二维网格中寻找连通区域的最大规模，核心是 **“标记已访问区域” 以避免重复计算 **。

初级思路：暴力遍历 + 标记

遍历每个格子，遇到 “陆地（1）” 就向上下左右扩展，同时将访问过的陆地置为 “水（0）”（相当于 “淹没”，避免重复遍历）。

// 全局变量记录当前岛屿面积和最大面积 int count = 0, ret = 0, m, n; void dfs(vector<vector<int>>& grid, int x, int y) { // 越界或非陆地，直接返回 if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) return; // 标记为已访问（淹没） grid[x][y] = 0; count++; // 当前岛屿面积+1 // 向四个方向扩展 dfs(grid, x+1, y); dfs(grid, x-1, y); dfs(grid, x, y+1); dfs(grid, x, y-1); } int maxAreaOfIsland(vector<vector<int>>& grid) { m = grid.size(), n = grid[0].size(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { count = 0; // 新岛屿重置计数 dfs(grid, i, j); ret = max(ret, count); // 更新最大面积 } } } return ret; }

深度思考：为什么用 “淹没” 而不是额外数组标记？

• 常规 DFS 会用visited数组标记已访问区域，但本题中将陆地置为 0 的 “原地修改”更优：
  1. 节省空间（无需额外 O (mn) 的数组）；
  2. 逻辑更直接（陆地被 “淹没” 后，后续遍历不会重复处理）。

206. 反转链表：递归的 “后序思维”

问题本质

将链表的 “指向关系” 反转 —— 每个节点的next指针从 “指向下一个节点” 改为 “指向前一个节点”。

初级思路：迭代法（双指针）

用pre和cur两个指针，遍历链表时不断修改cur->next的指向：

ListNode* reverseList(ListNode* head) { ListNode *pre = nullptr, *cur = head; while (cur != nullptr) { ListNode* next = cur->next; // 保存下一个节点 cur->next = pre; // 反转指向 pre = cur; // pre后移 cur = next; // cur后移 } return pre; }

进阶思路：递归法（后序遍历）

递归的核心是 **“从后往前” 处理节点 **—— 先递归到链表尾部，再反向修改next指针：

ListNode* reverseList(ListNode* head) { // 递归终止条件：空链表或只有一个节点 if (head == nullptr || head->next == nullptr) return head; // 递归到最后一个节点（新头节点） ListNode* newHead = reverseList(head->next); // 后序操作：修改当前节点的next指向 head->next->next = head; // 让下一个节点指向自己 head->next = nullptr; // 断开原指向（避免环） return newHead; }

深度思考：递归的 “后序” 价值

递归反转链表的关键是 **“后序遍历”**：

• 递归调用是 “递” 的过程（走到链表尾部）；
• 修改next指针是 “归” 的过程（从尾部往头部反向修改指向）。这种思路避免了迭代法中 “保存下一个节点” 的操作，逻辑更简洁，但需要理解递归的 “栈帧” 执行顺序。

135. 分发糖果：贪心的 “两次遍历” 思维

问题本质

在两个约束条件（每个孩子至少 1 颗、评分高的孩子比邻居多）下，求 “最少糖果数”—— 本质是局部最优→全局最优的贪心策略。

错误思路：单次遍历

如果只从左到右遍历，会忽略 “右边孩子评分比左边高” 的情况（比如[1,3,2]，单次遍历会得到[1,2,1]，但正确结果是[1,2,1]，但如果是[1,2,3,2,1]，单次遍历会错误计算）。

正确思路：两次贪心遍历

1. 左→右遍历：保证 “右边评分高的孩子比左边多”；
2. 右→左遍历：保证 “左边评分高的孩子比右边多”；最终取两次遍历的最大值，满足两个约束条件。

int candy(vector<int>& ratings) { int n = ratings.size(); vector<int> candies(n, 1); // 每个孩子至少1颗 // 左→右：右边比左边高，糖果+1 for (int i = 1; i < n; i++) { if (ratings[i] > ratings[i-1]) { candies[i] = candies[i-1] + 1; } } // 右→左：左边比右边高，取当前值和右边+1的最大值 for (int i = n-2; i >= 0; i--) { if (ratings[i] > ratings[i+1]) { candies[i] = max(candies[i], candies[i+1] + 1); } } // 求和 int total = 0; for (int num : candies) total += num; return total; }

深度思考：为什么需要两次遍历？

贪心算法的核心是 **“每次只满足一个约束”**：

• 左→右遍历只能保证 “左边约束”（右边比左边高）；
• 右→左遍历才能补充 “右边约束”（左边比右边高）；两次遍历后，每个孩子的糖果数同时满足两个约束，且是 “最少” 的（因为每次只在必要时增加糖果数）。

写在最后：算法思路的 “深度” 是什么？

从这 3 道题可以看出，算法的 “深度” 不是 “写出更复杂的代码”，而是：

1. 空间优化：如岛屿问题中用 “原地修改” 代替额外数组；
2. 思维转换：如反转链表中用 “后序递归” 代替迭代；
3. 约束拆分：如分发糖果中用 “两次遍历” 拆分两个约束。