给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
这道题我一个想到的是横向的计算，但是时间太长
接雨水（从“横向切分”到“纵向双指针”的思维演进）
方案一：横向切分（按行求水）
1. 算法核心思想：切蛋糕法
这是一种极其符合人类物理直觉的解法。我们把整个地形想象成一个积木，从高度为 1 的底层开始，一层一层向上“横向切割”，一直切到最高的那根柱子的顶部。
- 对于单独的每一层（高度设为
i），我们先从左到右找到第一个能挡水的高度（左边界start），再从右到左找到第一个能挡水的高度（右边界end）。 - 在这两个边界内部，只要真实的柱子高度小于当前层的高度
i，这就必然是一个能装 1 格水的空缺。
class Solution {
public:
int trap(vector<int>& height) {
if (height.empty()) return 0;
int count = 0;
int heightMax = 0;
// 1. 找出整个地形的最高峰
for (int i = 0; i < height.size(); i++) {
if (height[i] > heightMax) {
heightMax = height[i];
}
}
// 2. 从高度 1 开始，一层一层往上横向扫描
for (int i = 1; i <= heightMax; i++) {
int start = 0, end = height.size() - 1;
// 找当前层的左侧兜底边界
while (start < height.size() && height[start] < i) {
start++;
}
// 找当前层的右侧兜底边界
while (end >= 0 && height[end] < i) {
end--;
}
// 在有效边界内，计算空缺的水格
for (int j = start; j <= end; j++) {
if (height[j] < i) {
count++;
}
}
}
return count;
}
};
3. 复杂度剖析与局限性
- 时间复杂度：O(N×H)。其中 N 是数组长度，H 是最大高度
heightMax。这种解法在高度 H 较小时运行完美，但在极端测试用例（如柱子极高，且交错出现）中，会导致循环次数激增，最终触发 Time Limit Exceeded (TLE，超出时间限制)。 - 空间复杂度：O(1)。没有使用额外的数据结构。
💡 题解：接雨水（从“横向切分”到“纵向双指针”的思维演进）
解决接雨水问题，本质上是在计算复杂地形中的“有效凹陷面积”。我们在思考这道题时，经历了从“按行切分（直观物理模拟）”到“按列计算（数学极限降维）”的思维跨越。
方案一：横向切分（按行求水）—— 直观但触碰性能天花板
1. 算法核心思想：切蛋糕法
这是一种极其符合人类物理直觉的解法。我们把整个地形想象成一个积木，从高度为 1 的底层开始，一层一层向上“横向切割”，一直切到最高的那根柱子的顶部。
- 对于单独的每一层（高度设为
i），我们先从左到右找到第一个能挡水的高度（左边界start），再从右到左找到第一个能挡水的高度（右边界end）。 - 在这两个边界内部，只要真实的柱子高度小于当前层的高度
i，这就必然是一个能装 1 格水的空缺。
2.代码实现
class Solution {
public:
int trap(vector<int>& height) {
if (height.empty()) return 0;
int count = 0;
int heightMax = 0;
// 1. 找出整个地形的最高峰
for (int i = 0; i < height.size(); i++) {
if (height[i] > heightMax) {
heightMax = height[i];
}
}
// 2. 从高度 1 开始，一层一层往上横向扫描
for (int i = 1; i <= heightMax; i++) {
int start = 0, end = height.size() - 1;
// 找当前层的左侧兜底边界
while (start < height.size() && height[start] < i) {
start++;
}
// 找当前层的右侧兜底边界
while (end >= 0 && height[end] < i) {
end--;
}
// 在有效边界内，计算空缺的水格
for (int j = start; j <= end; j++) {
if (height[j] < i) {
count++;
}
}
}
return count;
}
};
3. 复杂度剖析与局限性
- 时间复杂度：O(N×H)。其中 N 是数组长度，H 是最大高度
heightMax。这种解法在高度 H 较小时运行完美，但在极端测试用例（如柱子极高，且交错出现）中，会导致循环次数激增，最终触发 Time Limit Exceeded (TLE，超出时间限制)。 - 空间复杂度：O(1)。没有使用额外的数据结构。
方案二：纵向双指针（按列求水）
1. 算法核心思想：局部木桶效应
一根单独的柱子头顶能装多少水，完全取决于**“它左侧的最高峰（LeftMax）”与“它右侧的最高峰（RightMax）”中的较短者**。只要当前柱子的高度低于这个短板，就能装下两者差值的水量。
2. 双指针降维逻辑
与其针对每根柱子向两边寻找最高峰，不如使用双指针从两端向中间相向而行，一边走一边维护历史最高峰。
- 短板优先判断：比较
LeftMax和RightMax，哪边的最高峰更矮，哪边柱子的命运（蓄水量）就已经被锁死了，因为另一边一定存在一个更高的墙在兜底。 - 结算与更新：确定了短板一侧后，拿历史最高峰与脚下真实柱子比较。如果形成凹陷，直接结算接水量；如果脚下的柱子比历史最高峰还高，不仅接不到水，它还会成为新的最高峰，用于挡住后面的水。
class Solution {
public:
int trap(vector<int>& height) {
// 1. 防御边界数据：少于 3 根柱子无法形成坑洼接水
if (height.size() <= 2) {
return 0;
}
int sum = 0;
// 2. 记录初始左右两端的最高峰
int LeftMax = height[0];
int RightMax = height[height.size() - 1];
// 3. 双指针从两侧次边缘开始向中间逼近
int left = 1;
int right = height.size() - 2;
// 4. 确保左右指针相遇的最后一根柱子也能被结算
while (left <= right) {
// 左边是短板，左边命运确定
if (LeftMax < RightMax) {
if (LeftMax > height[left]) {
sum += (LeftMax - height[left]); // 遇到坑洼，算水
} else {
LeftMax = height[left]; // 遇到新高山，更新短板
}
left++;
}
// 右边是短板，右边命运确定
else {
if (RightMax > height[right]) {
sum += (RightMax - height[right]);
} else {
RightMax = height[right];
}
right--;
}
}
return sum;
}
};
4. 复杂度剖析
- 时间复杂度：O(N)。双指针遍历，数组中的每个元素最多被访问一次，直接降维打击，彻底解决超时问题。
- 空间复杂度：O(1)。仅维护了几个指针和极值变量，内存节约。