10.接雨水

---

✅ 解法一：双指针法（推荐）

⭐ 时间复杂度：O(n)，空间复杂度：O(1)

🌟 思路

左右指针从两边向中间移动，维护左右两边的最大值，用较小一边的最大值判断当前能接多少水。

💡 C++ 代码

class Solution {
public:int trap(vector<int>& height) {int left = 0, right = height.size() - 1;int leftMax = 0, rightMax = 0;int total = 0;while (left < right) {if (height[left] < height[right]) {if (height[left] >= leftMax) {leftMax = height[left];  // 更新左侧最大高度} else {total += leftMax - height[left];  // 计算当前位置能接的水}++left;} else {if (height[right] >= rightMax) {rightMax = height[right];  // 更新右侧最大高度} else {total += rightMax - height[right];  // 接水}--right;}}return total;}
};

---

✅ 解法二：动态规划法（前缀+后缀最大值预处理）

⭐ 时间复杂度：O(n)，空间复杂度：O(n)

🌟 思路

对每个位置计算「左边最大值」和「右边最大值」，然后计算该位置能接多少水。

💡 C++ 代码

class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n == 0) return 0;vector<int> leftMax(n), rightMax(n);leftMax[0] = height[0];for (int i = 1; i < n; ++i) {leftMax[i] = max(leftMax[i - 1], height[i]);}rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i) {rightMax[i] = max(rightMax[i + 1], height[i]);}int total = 0;for (int i = 0; i < n; ++i) {total += min(leftMax[i], rightMax[i]) - height[i];}return total;}
};

---

✅ 解法三：单调栈

⭐ 时间复杂度：O(n)，空间复杂度：O(n)

🌟 思路解析：

我们维护一个单调递减栈，栈中存放的是下标索引。当我们遇到一个比栈顶元素高的柱子时，说明形成了一个可接雨水的凹槽结构，这时候计算能接多少水。

📌 举个例子：

• 当前柱子是右墙；
• 栈顶元素是低洼地（bottom）；
• 栈下一个元素是左墙；
• 用左、右墙的最小高度减去底部高度，即为这段的雨水量。

---

💡 C++ 代码 + 注释

class Solution {
public:int trap(vector<int>& height) {int n = height.size();stack<int> st;  // 存储下标int total = 0;for (int i = 0; i < n; ++i) {// 当前柱子比栈顶高，说明可以形成凹槽while (!st.empty() && height[i] > height[st.top()]) {int bottom = st.top();st.pop();if (st.empty()) break;  // 没有左边界，不能接水int left = st.top();int width = i - left - 1;  // 左右柱子之间的宽度int heightBound = min(height[left], height[i]) - height[bottom];  // 能装的水高total += width * heightBound;  // 计算雨水量}st.push(i);  // 当前柱子入栈}return total;}
};

---

✅ 三种主流解法对比总结：

解法	时间复杂度	空间复杂度	是否推荐	特点
双指针	O(n)	O(1)	✅ 最推荐	思路直观、代码简洁
动态规划	O(n)	O(n)	✅ 推荐	易理解、适合初学
单调栈	O(n)	O(n)	✅ 拓展	适合强化数据结构理解

---