多数元素
1. 题目回顾
题目描述：
给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。
约束条件：
- 你可以假设数组是非空的。
- 给定的数组总是存在多数元素。
示例：
- 输入：
nums = [2,2,1,1,1,2,2] - 输出：
2
2. 核心思路：频次统计与“两两抵消”
这道题是算法思维的经典训练场，主要分为两个层次的解法：
- 常规思维（哈希表计数）：最自然的想法是利用哈希表（HashMap）统计每个元素出现的频次，然后遍历哈希表找出频次大于
n/2的元素。这种方法逻辑清晰，但需要额外的空间来存储频次。 - 进阶思维（Boyer-Moore 摩尔投票法）：题目给出了一个极其强大的条件：“多数元素的数量严格大于其余所有元素的总和”。基于此，我们可以将问题转化为“两军对垒”：把多数元素看作“友军”，其他元素看作“敌军”。每遇到一个相同的元素，票数加一；遇到不同的元素，票数减一（相互抵消）。因为友军数量占绝对优势，即使不断抵消，最后剩下的“候选人”必定是多数元素。这种方法将空间复杂度降到了极致。
3. 算法详细步骤
3.1 哈希表法步骤
- 初始化：创建一个哈希表用于存储元素及其对应的出现次数。
- 遍历统计：遍历数组，若元素已在哈希表中，则其计数加 1；若不在，则将其加入哈希表并设置计数为 1。
- 查找返回：在遍历过程中或遍历结束后，检查当前元素的计数是否大于
n/2，满足条件则直接返回该元素。
3.2 摩尔投票法步骤
- 初始化状态：设定一个候选人
candidate（初始可为任意值）和一个计数器count（初始为 0）。 - 遍历数组：依次读取数组中的每一个元素：
- 如果
count == 0，说明之前的候选人已经被完全抵消，将当前元素设为新的候选人，并将count置为 1。 - 如果当前元素等于候选人，说明是“友军”，
count加 1。 - 如果当前元素不等于候选人，说明是“敌军”，
count减 1（发生抵消）。
- 如果
- 返回结果：遍历结束后，由于题目保证多数元素一定存在，当前保留的
candidate即为最终答案。（若题目不保证存在，则需再遍历一次验证其真实频次）。
4. 代码实现
以下是两种解法的 Java 代码实现：
解法一：哈希表法
class Solution { public int majorityElement(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); int n = nums.length; for (int num : nums) { // 获取当前元素的频次，若不存在则默认为0 int count = map.getOrDefault(num, 0) + 1; map.put(num, count); // 如果频次超过一半，直接返回 if (count > n / 2) { return num; } } return -1; // 理论上不会执行到这里 } }解法二：摩尔投票法（最优解）
class Solution { public int majorityElement(int[] nums) { int candidate = 0; int count = 0; for (int num : nums) { if (count == 0) { // 票数归零，更换候选人 candidate = num; count = 1; } else if (num == candidate) { // 遇到相同元素，票数加一 count++; } else { // 遇到不同元素，票数减一（相互抵消） count--; } } // 题目保证多数元素一定存在，直接返回候选人 return candidate; } }5. 复杂度分析
哈希表法
- 时间复杂度： O(n)
只需要对数组进行一次线性遍历，每次哈希表的插入和查找操作平均时间复杂度为 O(1) 。 - 空间复杂度： O(n)
在最坏的情况下（例如数组前半部分全是不相同的元素），哈希表需要存储大约 n/2 个键值对，因此空间复杂度为线性级别。
摩尔投票法
- 时间复杂度： O(n)
同样只需要对数组进行一次线性遍历。 - 空间复杂度： O(1)
只使用了常数级别的额外空间（仅维护candidate和count两个变量），完美满足进阶要求。
接雨水
1. 题目回顾
题目描述：
给定n个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
核心概念：
- 木桶效应：对于任何一个位置，它能接住的水量取决于它左侧最高柱子和右侧最高柱子中较矮的那个（即“短板”）。
- 积水量计算：当前位置能接的水量 =
min(左侧最高, 右侧最高) - 当前位置高度（若结果为正，否则为 0）。
示例：
- 输入：
height = [0,1,0,2,1,0,1,3,2,1,2,1] - 输出：
6 - 解释：在这种高度排列下，凹陷处总共可以接 6 个单位的雨水。
2. 核心思路：双指针与贪心策略
这道题是算法面试中的经典高频题。相比于使用额外数组记录左右最大值的动态规划法，双指针法是空间复杂度最优的“天花板”解法。
- 核心洞察：每个位置的实际蓄水量是由左右两侧最大值中较小的那个决定的。这意味着，如果我们已经知道了左右两侧最大值中较小的那一个，我们就能立刻确定当前短板侧当前位置的积水量，而无需知道另一侧完整的最大值。
- 贪心策略：使用左右双指针向中间逼近，总是优先处理最大值较小的一侧。因为该侧的蓄水量已经可以确定，处理完后移动指针即可。这种“走一步看一步，优先处理短板”的贪心策略，使得我们可以在 O(1)O(1) 的空间内完成计算。
3. 算法详细步骤
3.1 初始化状态
- 设定左指针
left = 0，右指针right = n - 1。 - 设定两个变量
leftMax = 0和rightMax = 0，分别记录左指针左侧（含自身）的历史最大高度，以及右指针右侧（含自身）的历史最大高度。 - 初始化总积水量
ans = 0。
3.2 双指针向中间移动
当left < right时，持续进行以下操作：
- 更新历史最大值：每次移动指针前，先用当前柱子的高度更新对应侧的
leftMax或rightMax。 - 比较并结算短板：
- 如果
leftMax < rightMax：说明左侧是短板。此时左指针位置的积水量已确定为leftMax - height[left]。将其累加到ans，并将左指针右移（left++）。 - 否则（
rightMax <= leftMax）：说明右侧是短板。此时右指针位置的积水量已确定为rightMax - height[right]。将其累加到ans，并将右指针左移（right--）。
- 如果
3.3 返回结果
当左右指针相遇时，说明所有位置都已处理完毕，返回累加的总和ans。
4. 代码实现
以下是基于双指针法的 Java 代码实现，包含了详细的逻辑注释：
class Solution { public int trap(int[] height) { // 初始化总积水量 int ans = 0; // 初始化左右双指针，分别指向数组的头和尾 int left = 0; int right = height.length - 1; // 记录左指针左侧（含自身）的历史最大高度 int leftMax = 0; // 记录右指针右侧（含自身）的历史最大高度 int rightMax = 0; // 当左右指针未相遇时，持续向中间逼近 while (left < right) { // 1. 更新当前左右指针位置遇到的历史最大高度 leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); // 2. 核心贪心策略：优先处理较小的一侧（短板决定蓄水量） if (leftMax < rightMax) { // 左侧是短板： // 因为右侧至少有一个 rightMax 的柱子，而左侧最高只有 leftMax， // 所以左指针当前位置的水位最高只能被托到 leftMax。 // 积水量 = 左侧天花板 - 当前柱子高度 ans += leftMax - height[left]; // 左指针当前位置处理完毕，向右移动 left++; } else { // 右侧是短板（或左右天花板相等）： // 同理，右指针当前位置的水位由 rightMax 决定。 // 积水量 = 右侧天花板 - 当前柱子高度 ans += rightMax - height[right]; // 右指针当前位置处理完毕，向左移动 right--; } } // 3. 返回最终累加的总积水量 return ans; } }5. 复杂度分析
假设数组的长度为 n 。
- 时间复杂度： O(n)
左右指针总共移动 nn 次，每次操作（更新最大值、计算积水量、移动指针）的时间复杂度均为 O(1)。 - 空间复杂度： O(1)
只使用了常数级别的额外空间（left,right,leftMax,rightMax,ans这五个变量），是空间最优的解法。
