南昌房产网官方_新颖网站页面设计_北京seo顾问服务_关键词查询神器

力扣HOT100 - 1. 两数之和
在这里插入图片描述
解题思路：

解法一：暴力

class Solution {public int[] twoSum(int[] nums, int target) {int n = nums.length;for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++) {if (target == nums[i] + nums[j])return new int[] { i, j };}return new int[0];}
}

解法二：哈希表

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; ++i) {if (map.containsKey(target - nums[i])) {//保证返回的下标由小到大return new int[]{map.get(target - nums[i]), i};}map.put(nums[i], i);}return new int[0];}
}

解析：
这段代码实现的是经典的 两数之和（Two Sum） 算法，通过使用哈希表（HashMap）来优化时间复杂度。以下是对代码的详细解析：

代码功能

输入：一个整数数组 nums 和一个目标值 target。
输出：返回数组中两个不同下标 i 和 j，使得 nums[i] + nums[j] == target。
- 如果存在解，保证返回的下标 i < j（按升序排列）。
- 如果无解，返回空数组 new int[0]。

算法思路

哈希表辅助：
- 使用 HashMap 存储数组元素值 (nums[i]) 和对应的下标 (i)。
- 对于当前元素 nums[i]，检查 target - nums[i] 是否已存在于哈希表中：
  - 如果存在，说明找到了这两个数，直接返回它们的下标。
  - 如果不存在，将当前 nums[i] 和 i 存入哈希表，继续遍历。
时间复杂度：
- O(n)：只需遍历数组一次，哈希表的插入和查询操作平均为 O(1)。
- 比暴力解法（O(n²)）更高效。
空间复杂度：
- O(n)：最坏情况下需要存储所有元素到哈希表。

代码逐行解析

public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();  // 键：数组元素值，值：下标for (int i = 0; i < nums.length; ++i) {if (map.containsKey(target - nums[i])) {  // 检查是否已有互补数return new int[]{map.get(target - nums[i]), i};  // 返回升序下标}map.put(nums[i], i);  // 存入当前数和下标}return new int[0];  // 无解时返回空数组
}

关键点

为什么能保证下标升序？
- 当发现 target - nums[i] 在哈希表中时，该数一定是在 nums[i] 之前被存入的（因为当前 nums[i] 还未存入）。
- 因此 map.get(target - nums[i]) 获取的下标一定小于 i，直接返回 {map.get(...), i} 即满足升序。
如何处理重复元素？
- 例如 nums = [3, 3], target = 6：
  - 第一个 3 存入哈希表（map = {3: 0}）。
  - 第二个 3 时，target - 3 = 3 已在哈希表中，直接返回 [0, 1]。
- 注意：如果问题要求不能重复使用同一元素（如 nums = [3], target = 6），需额外判断（但本题约束保证解存在或唯一）。
为什么返回 new int[0] 而不是 null？
- 空数组更安全，调用方无需判空，可直接通过 result.length == 0 判断无解。

示例运行

输入：nums = [2, 7, 11, 15], target = 9
- 步骤：
  1. i=0：2 的互补数 7 不在哈希表 → 存入 {2: 0}。
  2. i=1：7 的互补数 2 在哈希表 → 返回 [0, 1]。
输入：nums = [3, 2, 4], target = 6
- 返回 [1, 2]（因为 2 + 4 = 6，且下标升序）。

边界情况

无解时：如 nums = [1, 2], target = 4 → 返回 []。
重复元素：如 nums = [3, 3], target = 6 → 返回 [0, 1]。
负数或零：如 nums = [-1, 0], target = -1 → 返回 [0, 1]。

优化与变种

提前返回：一旦找到解立即返回，减少不必要的遍历。
处理重复元素：如果问题要求所有可能的解（不止一个），可以用 List 存储结果。
排序+双指针：如果需返回数值而非下标，可先排序后用双指针（但会改变下标信息）。

总结

该实现是两数之和问题的最优解之一，兼顾了时间复杂度和代码简洁性。
核心思想：用空间换时间，通过哈希表避免嵌套循环。

如果有其他变种问题（如三数之和、允许重复使用元素等），可以进一步讨论！

力扣HOT100 - 49. 字母异位词分组
在这里插入图片描述
注意：
返回时不能用List，因为List是抽象类，return的必须是List的具体实现，如ArrayList

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str : strs) {char[] array = str.toCharArray();Arrays.sort(array);String key = new String(array);List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str);map.put(key, list);}//返回时不能用List，而必须是List的具体实现，如ArrayListreturn new ArrayList<List<String>>(map.values());}
}

解析：
这段代码实现的是 字母异位词分组（Group Anagrams） 问题，通过将每个字符串排序后的结果作为键，将字母异位词归类到同一个列表中。以下是详细解析：

问题描述

输入：一个字符串数组 strs（例如 ["eat","tea","tan","ate","nat","bat"]）。
输出：将字母异位词（由相同字母重排列组成的字符串）分到同一组，返回分组后的列表（如 [["eat","tea","ate"], ["tan","nat"], ["bat"]]）。

算法思路

哈希表分组：
- 使用 HashMap，键是 排序后的字符串（字母异位词排序后相同），值是对应的原始字符串列表。
- 遍历每个字符串，先排序其字符数组，生成统一的键，再将原始字符串加入对应的列表。
关键操作：
- 排序字符数组：将字符串转换为 char[] 并排序，使得字母异位词具有相同的键（如 "eat" 和 "tea" 均排序为 "aet"）。
- 哈希表管理：使用 map.getOrDefault() 避免重复创建列表。
复杂度分析：
- 时间复杂度：O(n * k log k)，其中 n 是数组长度，k 是字符串最大长度（排序每个字符串的代价）。
- 空间复杂度：O(n * k)，哈希表存储所有字符串。

代码逐行解析

public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();  // 键：排序后的字符串，值：原始字符串列表for (String str : strs) {char[] array = str.toCharArray();  // 转为字符数组Arrays.sort(array);                // 排序（字母异位词排序后相同）String key = new String(array);    // 生成统一键List<String> list = map.getOrDefault(key, new ArrayList<String>()); // 获取或新建列表list.add(str);                     // 加入当前字符串map.put(key, list);                // 更新哈希表}return new ArrayList<List<String>>(map.values()); // 返回所有分组
}

关键点

为什么排序字符数组？
- 字母异位词排序后结果相同（如 "eat" → "aet"，"tea" → "aet"），可作为分组的唯一标识。
map.getOrDefault() 的作用：
- 若键不存在，返回默认值（新建的 ArrayList）；若存在，直接返回对应的列表。避免手动检查键是否存在。
返回值处理：
- map.values() 返回所有分组的集合，通过 new ArrayList<>(...) 包装成 List<List<String>> 类型。

示例运行

输入：strs = ["eat","tea","tan","ate","nat","bat"]
- 步骤：
  1. "eat" → 排序为 "aet" → 新建列表 ["eat"]。
  2. "tea" → 排序为 "aet" → 加入列表 ["eat", "tea"]。
  3. "tan" → 排序为 "ant" → 新建列表 ["tan"]。
  4. 最终分组：{"aet": ["eat","tea","ate"], "ant": ["tan","nat"], "abt": ["bat"]}。
- 输出：[["eat","tea","ate"], ["tan","nat"], ["bat"]]。

优化与变种

优化键的生成：
- 若字符串只含小写字母，可用 字符计数数组 作为键（如 "aab" 表示为 [2,1,0,...,0]），避免排序开销：
```
int[] count = new int[26];
for (char c : str.toCharArray()) count[c - 'a']++;
String key = Arrays.toString(count);  // 将计数数组转为字符串作为键
```
  - 时间复杂度降至 O(n * k)。
处理大写/特殊字符：
- 扩展字符计数数组的长度（如 ASCII 码范围）。
返回其他结构：
- 若需按组内字符串数量排序，可对 map.values() 进行排序。

边界情况

空数组输入：strs = [] → 返回 []。
所有字符串相同：strs = ["a","a"] → 返回 [["a","a"]]。
无字母异位词：strs = ["a","b"] → 返回 [["a"], ["b"]]。

总结

该解法通过 排序统一键 或 字符计数 高效分组，是字母异位词问题的标准解法。
选择排序还是计数取决于字符集大小（小写字母优先用计数）。

如果有其他需求（如按字典序输出分组），可以进一步调整！

力扣HOT100 - 128. 最长连续序列
在这里插入图片描述
解题思路：

注意：

1.Set不能直接排序，必须要转换成ArrayList或者LinkedList后用Collections.sort()方法进行排序。

（Queue也不能直接排序，排序方法同Set）

2.连续的序列不能只找第一个，因为不一定是最长的，需要全部遍历完才能找到最长序列。

class Solution {public int longestConsecutive(int[] nums) {if (nums.length == 0)  return 0;Set<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {set.add(nums[i]);}List<Integer> list = new ArrayList<>(set);Collections.sort(list);//cnt的长度从1开始，本身长度为1int cnt = 1;int max = 0;//减一是为了避免越界for (int i = 0; i < list.size() - 1; i++) {if (list.get(i) == list.get(i + 1) - 1) {cnt++;} else {max = Math.max(cnt, max);//重置cnt的值cnt = 1;}}max = Math.max(cnt, max);return max;}
}```
解析：
这段代码实现了 **最长连续序列（Longest Consecutive Sequence）** 问题，但存在一些可以优化的地方。以下是详细解析和改进建议：---### **原代码分析**
#### **思路**
1. **去重**：使用 `HashSet` 去除重复数字。
2. **排序**：将去重后的数字存入 `ArrayList` 并排序。
3. **遍历统计**：检查相邻数字是否连续，统计最长连续序列长度。#### **复杂度**
- **时间复杂度**：O(n log n)，主要由排序步骤决定（`Collections.sort()`）。
- **空间复杂度**：O(n)，用于存储去重后的数字。#### **问题**
- **排序不必要**：题目要求连续序列（如 `[1,2,3]`），但排序增加了时间复杂度。
- **边界处理冗余**：末尾需要额外 `Math.max(cnt, max)` 处理最后一个连续序列。---### **优化思路**
利用 **哈希集合** 直接寻找连续序列的起点，避免排序：
1. **将所有数字存入集合**（去重）。
2. **遍历集合**，仅当当前数字 `num` 是某个连续序列的起点（即 `num-1` 不在集合中）时，向后检查 `num+1, num+2,...` 是否存在，统计长度。
3. **更新最大值**。#### **优化后复杂度**
- **时间复杂度**：O(n)，每个数字最多被访问两次（一次在集合中，一次在连续序列检查中）。
- **空间复杂度**：O(n)。---### **优化后的代码**
```java
class Solution {public int longestConsecutive(int[] nums) {if (nums.length == 0) return 0;Set<Integer> set = new HashSet<>();for (int num : nums) {set.add(num); // 去重}int maxLen = 1;for (int num : set) {// 只有当 num 是连续序列的起点时才检查（避免重复计算）if (!set.contains(num - 1)) {int currentNum = num;int currentLen = 1;// 向后查找连续的数字while (set.contains(currentNum + 1)) {currentNum++;currentLen++;}maxLen = Math.max(maxLen, currentLen);}}return maxLen;}
}

关键改进点

避免排序：直接利用集合的 O(1) 查询特性。
高效检查连续序列：仅对可能的序列起点（num-1 不在集合中）进行检查。
边界处理简化：无需处理排序后的末尾特殊情况。

示例运行

输入：nums = [100, 4, 200, 1, 3, 2]
- 步骤：
  1. 集合：{1, 2, 3, 4, 100, 200}。
  2. 检查起点：
    - 1（0 不在集合中）→ 连续序列 1,2,3,4，长度 4。
    - 100（99 不在集合中）→ 连续序列 100，长度 1。
    - 200（199 不在集合中）→ 连续序列 200，长度 1。
- 输出：4。

边界情况

空数组：直接返回 0。
所有数字相同：如 [1,1,1] → 去重后 [1]，返回 1。
无连续序列：如 [5, 7, 9] → 每个数字单独成组，返回 1。

总结

原始代码：通过排序解决问题，但时间复杂度过高（O(n log n)）。
优化后代码：利用哈希集合将时间复杂度降至 O(n)，更高效。
适用场景：当输入规模较大时（如 n > 10^5），优化后的方法优势明显。

力扣HOT100 - 283. 移动零
在这里插入图片描述
解题思路：

双指针

指针 i 用于寻找不为零的位置

指针 j 用于寻找为零的位置

找到不为零时位置时与为零的位置进行交换，即nums[ i ]与nums[ j ]交换，使零向后移动，i 和 j 同时向下一个位置移动。

class Solution {public void moveZeroes(int[] nums) {if (nums == null) return;            int j = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {int tmp = nums[i];nums[i] = nums[j];nums[j++] = tmp;//j++所到的位置还是零}}}
}

力扣HOT100 - 11. 盛最多水的容器
在这里插入图片描述
解析

class Solution {public int maxArea(int[] height) {int i = 0, j = height.length - 1, res = 0;while(i < j) {res = height[i] < height[j] ? Math.max(res, (j - i) * height[i++]): Math.max(res, (j - i) * height[j--]); }return res;}
}

易错点：Math.max(res , (j - i) * height[i++])和Math.max(res , height[i++] * (j - i) )结果不同

这两个表达式的结果不同，是因为 i++ 的自增操作时机影响了 (j - i) 的计算结果。具体差异如下：

**表达式 1：`Math.max(res, (j - i) * height[i++])`**

执行顺序：
- 先计算 (j - i)（此时 i 未自增）。
- 再计算 height[i]（此时 i 仍未自增）。
- 最后进行 i++（自增发生在整个表达式计算完成后）。

等效代码：

int old_i = i;                // 保存当前i的值
int width = j - old_i;        // 宽度计算使用旧的i
int h = height[old_i];        // 高度使用旧的i
i = old_i + 1;                // i自增
res = Math.max(res, width * h);

**表达式 2：`Math.max(res, height[i++] * (j - i))`**

执行顺序：
- 先计算 height[i]（此时 i 未自增）。
- 然后执行 i++（自增立即发生，影响后续的 (j - i)）。
- 最后计算 (j - i)（此时 i 已经自增，宽度比预期少1）。

等效代码：

int old_i = i;                // 保存当前i的值
int h = height[old_i];        // 高度使用旧的i
i = old_i + 1;                // i自增（立即生效）
int width = j - i;            // 宽度计算使用新的i（比预期少1）
res = Math.max(res, h * width);

关键区别

表达式	`(j - i)` 的计算时机	`height[i]` 的索引	实际效果
`(j - i) * height[i++]`	在 `i++` 之前	原 `i`	宽度正确，高度正确
`height[i++] * (j - i)`	在 `i++` 之后	原 `i`	高度正确，宽度少1

示例说明

假设 i = 2, j = 5, height = [1, 3, 2, 4]：

表达式 1：
- (j - i) → 5 - 2 = 3
- height[i] → height[2] = 2
- 结果：3 * 2 = 6（正确）
- 执行后 i = 3。
表达式 2：
- height[i] → height[2] = 2
- i++ → i 变为 3
- (j - i) → 5 - 3 = 2
- 结果：2 * 2 = 4（宽度少1，错误）
- 执行后 i = 3。

如何避免问题？

分离自增操作：

int h = height[i];
i++;
res = Math.max(res, (j - i + 1) * h); // 注意宽度补偿

使用 i+1 显式计算：

res = Math.max(res, (j - (i + 1)) * height[i]);
i++;

总结

运算符优先级和求值顺序：i++ 的副作用会影响同一表达式中其他部分的计算。
防御性编程：在复杂表达式中，避免混用自增操作和依赖变量值的计算。

这种差异常见于双指针或滑动窗口算法中（如盛水容器问题）。务必确保宽度和高度的计算基于正确的索引！

力扣HOT100 - 15. 三数之和
在这里插入图片描述

解题思路：

排序 + 双指针
在这里插入图片描述

代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for(int k = 0; k < nums.length - 2; k++){if(nums[k] > 0) break;if(nums[k] + nums[k+1] + nums[k+2] > 0) break;if(k > 0 && nums[k] == nums[k - 1]) continue;int i = k + 1,j = nums.length - 1;while(i < j){int sum = nums[k] + nums[i] + nums[j];if(sum < 0){while(i < j && nums[i] == nums[++i]);} else if (sum > 0){while(i < j && nums[j] == nums[--j]);} else {res.add(new ArrayList<Integer>(Arrays.asList(nums[k],nums[i],nums[j])));while(i < j && nums[i] == nums[++i]);while(i < j && nums[j] == nums[--j]);}}}return res;}
}

这段代码实现了经典的 三数之和（3Sum） 问题，通过排序和双指针技巧高效地找到所有不重复的三元组 [nums[k], nums[i], nums[j]]，使得它们的和为 0。以下是对代码的详细解析：

算法思路

排序：
- 首先将数组排序，使得相同的数字相邻，方便后续去重和双指针移动。
外层循环固定第一个数（nums[k]）：
- 遍历 k 从 0 到 nums.length - 3（因为需要至少三个数）。
- 提前终止：如果 nums[k] > 0，由于数组已排序，后续数字更大，不可能再找到和为 0 的三元组，直接 break。
- 去重：如果 nums[k] == nums[k-1]，跳过以避免重复解。
内层双指针（i 和 j）：
- 初始化 i = k + 1（左指针），j = nums.length - 1（右指针）。
- 计算当前和 sum = nums[k] + nums[i] + nums[j]：
  - 如果 sum < 0，说明需要更大的数，左指针右移（i++）。
  - 如果 sum > 0，说明需要更小的数，右指针左移（j--）。
  - 如果 sum == 0，记录解，并跳过所有重复的 nums[i] 和 nums[j]。

代码逐行解析

public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums); // 排序，便于去重和双指针操作List<List<Integer>> res = new ArrayList<>();for (int k = 0; k < nums.length - 2; k++) { // 固定第一个数 nums[k]if (nums[k] > 0) break; // 提前终止if (k > 0 && nums[k] == nums[k - 1]) continue; // 跳过重复的 nums[k]int i = k + 1, j = nums.length - 1; // 双指针初始化while (i < j) {int sum = nums[k] + nums[i] + nums[j];if (sum < 0) {while (i < j && nums[i] == nums[++i]); // 左指针右移并跳过重复} else if (sum > 0) {while (i < j && nums[j] == nums[--j]); // 右指针左移并跳过重复} else {res.add(Arrays.asList(nums[k], nums[i], nums[j])); // 找到解while (i < j && nums[i] == nums[++i]); // 跳过重复的 nums[i]while (i < j && nums[j] == nums[--j]); // 跳过重复的 nums[j]}}}return res;
}

关键点

去重逻辑：
- 外层循环：通过 nums[k] == nums[k-1] 跳过重复的 nums[k]。
- 内层双指针：在找到解或移动指针时，用 while 循环跳过重复值（如 nums[i] == nums[++i]）。
提前终止：
- 当 nums[k] > 0 时，由于数组已排序，后续数字更大，不可能再满足 sum == 0。
双指针的移动：
- sum < 0 时，i++（需要更大的数）；sum > 0 时，j--（需要更小的数）。

复杂度分析

时间复杂度：O(n²)，其中外层循环 O(n)，内层双指针 O(n)。
空间复杂度：O(1)（不考虑结果存储空间）。

示例运行

输入：nums = [-1, 0, 1, 2, -1, -4]
- 排序后：[-4, -1, -1, 0, 1, 2]
- 步骤：
  1. k=0（-4），i=1（-1），j=5（2），sum = -3 < 0 → i++。
  2. k=0，i=2（-1），j=5（2），sum = -3 < 0 → i++。
  3. k=1（-1），i=2（-1），j=5（2），sum = 0 → 记录 [-1, -1, 2]，跳过重复的 i 和 j。
  4. k=1，i=3（0），j=4（1），sum = 0 → 记录 [-1, 0, 1]。
- 输出：[[-1, -1, 2], [-1, 0, 1]]。

边界情况

无解：如 nums = [1, 2, 3] → 返回 []。
全零：如 nums = [0, 0, 0] → 返回 [[0, 0, 0]]。
重复解：如 nums = [-1, -1, 0, 1, 1] → 返回 [[-1, 0, 1]]（去重后）。

优化与变种

提前跳过无效 k：
- 如果 nums[k] + nums[k+1] + nums[k+2] > 0，可以直接 break（因为后续三数之和只会更大）。
哈希表解法：
- 可以用哈希表存储补数，但去重较复杂，且时间复杂度仍为 O(n²)。

总结

该解法通过 排序 + 双指针 高效解决了三数之和问题，兼顾了时间复杂度和代码简洁性。重点在于 去重逻辑 和 双指针的移动策略。

力扣HOT100 - 42. 接雨水
在这里插入图片描述
解题思路：

1、动态规划
在这里插入图片描述

class Solution {public int trap(int[] height) {int n = height.length;if (n == 0) return 0;int[] leftMax = new int[n];leftMax[0] = height[0];for (int i = 1; i < n; i++) {leftMax[i] = Math.max(leftMax[i - 1], height[i]);}int[] rightMax = new int[n];rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = Math.max(rightMax[i + 1], height[i]);}int res = 0;for (int i = 0; i < n; i++) {res += Math.min(leftMax[i], rightMax[i]) - height[i];}return res;}
}

这段代码解决了 接雨水（Trapping Rain Water） 问题，通过动态规划预计算每个位置的左右最大高度，从而确定该位置能接的雨水量。以下是详细解析：

算法思路

动态规划预处理：
- leftMax 数组：leftMax[i] 表示位置 i **左侧（包括自身）**的最大高度。
  - 初始化：leftMax[0] = height[0]。
  - 递推：leftMax[i] = max(leftMax[i-1], height[i])。
- rightMax 数组：rightMax[i] 表示位置 i **右侧（包括自身）**的最大高度。
  - 初始化：rightMax[n-1] = height[n-1]。
  - 递推：rightMax[i] = max(rightMax[i+1], height[i])。
计算每个位置的雨水量：
- 对于位置 i，其雨水量由 min(leftMax[i], rightMax[i]) - height[i] 决定。
  - 即左右最大高度的较小值减去当前高度（木桶效应）。
汇总结果：累加所有位置的雨水量。

代码逐行解析

public int trap(int[] height) {int n = height.length;if (n == 0) return 0; // 边界条件// 1. 计算 leftMax 数组int[] leftMax = new int[n];leftMax[0] = height[0];for (int i = 1; i < n; i++) {leftMax[i] = Math.max(leftMax[i - 1], height[i]);}// 2. 计算 rightMax 数组int[] rightMax = new int[n];rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = Math.max(rightMax[i + 1], height[i]);}// 3. 计算总雨水量int res = 0;for (int i = 0; i < n; i++) {res += Math.min(leftMax[i], rightMax[i]) - height[i];}return res;
}

关键点

木桶效应：每个位置的雨水量由左右两侧最大高度的较小值决定。
预处理优化：通过动态规划将左右最大高度的计算从 O(n²) 优化到 O(n)。
边界处理：空数组直接返回 0。

复杂度分析

时间复杂度：O(n)，三次遍历数组（两次预处理，一次计算结果）。
空间复杂度：O(n)，用于存储 leftMax 和 rightMax 数组。

示例运行

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
- leftMax：[0,1,1,2,2,2,2,3,3,3,3,3]
- rightMax：[3,3,3,3,3,3,3,3,2,2,2,1]
- 计算：
  - i=2：min(1,3)-0 = 1
  - i=4：min(2,3)-1 = 1
  - i=5：min(2,3)-0 = 2
  - 其他位置贡献为 0。
- 输出：6（总雨水量）。

优化空间

双指针法：用两个指针代替 leftMax 和 rightMax 数组，空间复杂度降至 O(1)。

int left = 0, right = n - 1;
int leftMax = 0, rightMax = 0;
int res = 0;
while (left < right) {if (height[left] < height[right]) {leftMax = Math.max(leftMax, height[left]);res += leftMax - height[left];left++;} else {rightMax = Math.max(rightMax, height[right]);res += rightMax - height[right];right--;}
}

单调栈法：按行计算雨水量，适合理解但实现稍复杂。

边界情况

空数组或单元素：直接返回 0。
单调递增/递减：如 [1,2,3] 或 [3,2,1]，雨水量为 0。
平坦地形：如 [2,2,2]，雨水量为 0。

总结

该解法通过动态规划预处理左右最大高度，清晰高效地解决了问题。若需进一步优化空间，可采用双指针法。理解 木桶效应 和 预处理思想 是关键！

2、双指针解法

class Solution {public int trap(int[] height) {int left = 0, right = height.length - 1;int leftMax = 0, rightMax = 0;int res = 0;while (left < right) {if (height[left] < height[right]) {leftMax = Math.max(leftMax, height[left]);res += leftMax - height[left];left++;} else {rightMax = Math.max(rightMax, height[right]);res += rightMax - height[right];right--;}}return res;}
}

这段代码实现了 接雨水（Trapping Rain Water） 问题的 双指针解法，通过动态维护左右两侧的最大高度来高效计算雨水量。以下是详细解析：

算法思路

双指针初始化：
- left 从数组开头（0）向右移动，right 从末尾（height.length - 1）向左移动。
- leftMax 和 rightMax 分别记录遍历过程中左侧和右侧的最大高度（初始为 0）。
指针移动规则：
- 左指针右移：当 height[left] < height[right] 时，说明左侧的瓶颈高度由 leftMax 决定。
  - 更新 leftMax 为当前最大值。
  - 计算当前位置的雨水量：leftMax - height[left]（若 leftMax > height[left]）。
- 右指针左移：反之，右侧的瓶颈高度由 rightMax 决定，类似处理。
终止条件：当 left 和 right 相遇时结束。

代码逐行解析

public int trap(int[] height) {int left = 0, right = height.length - 1; // 初始化双指针int leftMax = 0, rightMax = 0;          // 记录左右最大高度int res = 0;                            // 总雨水量while (left < right) {if (height[left] < height[right]) {  // 左指针右移leftMax = Math.max(leftMax, height[left]);res += leftMax - height[left];   // 计算当前雨水量left++;} else {                            // 右指针左移rightMax = Math.max(rightMax, height[right]);res += rightMax - height[right];right--;}}return res;
}

关键点

木桶效应：每个位置的雨水量由 min(leftMax, rightMax) 决定，但通过双指针的移动规则，可以隐式保证：
- 当 height[left] < height[right] 时，leftMax < rightMax，因此 min(leftMax, rightMax) = leftMax。
- 反之同理。
指针移动逻辑：
- 总是移动高度较小的一侧指针，因为当前较小高度决定了当前位置的雨水上限。
时间复杂度优化：避免了预计算 leftMax 和 rightMax 数组，空间复杂度从 O(n) 降至 O(1)。

示例运行

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
- 步骤：
  1. left=0（0），right=11（1）：0 < 1 → 左指针右移，leftMax=0，res+=0，left=1。
  2. left=1（1），right=11（1）：1 == 1 → 右指针左移，rightMax=1，res+=0，right=10。
  3. left=1（1），right=10（2）：1 < 2 → 左指针右移，leftMax=1，res+=0，left=2。
  4. left=2（0），right=10（2）：0 < 2 → 左指针右移，leftMax=1，res+=1，left=3。
  - 最终累计 res = 6。

复杂度分析

时间复杂度：O(n)，仅需一次遍历。
空间复杂度：O(1)，仅使用常数额外空间。

对比动态规划解法

方法	时间复杂度	空间复杂度	核心思想
动态规划	O(n)	O(n)	预处理左右最大高度数组
双指针	O(n)	O(1)	边遍历边维护左右最大高度

双指针法在空间上更优，适合大规模数据。

边界情况

空数组或单元素：直接返回 0（循环不会执行）。
单调递增/递减：如 [1,2,3] 或 [3,2,1]，雨水量为 0。
平坦地形：如 [2,2,2]，雨水量为 0。

常见问题

Q1：为什么移动较小高度的指针？

因为较小高度决定了当前位置的雨水上限（木桶效应）。移动较小指针可以确保另一侧的最大高度足够高。

Q2：如何保证 leftMax 和 rightMax 的正确性？

每次移动指针时，先更新对应方向的最大高度，再计算雨水量。确保计算时另一侧的最大高度一定不小于当前方向的最大高度。

总结

双指针法通过 动态维护左右最大高度 和 智能移动指针，高效解决了接雨水问题。其核心在于理解 木桶效应 和 指针移动的合理性。

南昌房产网官方_新颖网站页面设计_北京seo顾问服务_关键词查询神器

代码功能

算法思路

代码逐行解析

关键点

示例运行

边界情况

优化与变种

总结

问题描述

算法思路

代码逐行解析

关键点

示例运行

优化与变种

边界情况

总结

关键改进点

示例运行

边界情况

总结

表达式 1：Math.max(res, (j - i) * height[i++])

表达式 2：Math.max(res, height[i++] * (j - i))

关键区别

示例说明

如何避免问题？

总结

算法思路

代码逐行解析

关键点

复杂度分析

示例运行

边界情况

优化与变种

总结

算法思路

代码逐行解析

关键点

复杂度分析

示例运行

优化空间

边界情况

总结

算法思路

代码逐行解析

关键点

示例运行

复杂度分析

对比动态规划解法

边界情况

常见问题

总结

**表达式 1：`Math.max(res, (j - i) * height[i++])`**

**表达式 2：`Math.max(res, height[i++] * (j - i))`**