题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
数据范围
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
样例
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
代码
博主的垃圾代码，是在没考虑，动态规划，单调栈，以及双指针优化的情况下写的 O（n2），博主引以为鉴，不动脑的后果，大家不必观看。
package leetcode100;
/**
* @author akuya
* @create 2025-05-07-9:09
*/
public class seven {
public static void main(String[] args) {
int res= trap(new int[]{4,2,3});
System.out.println(res);
}
public static int trap(int[] height) {
int len=height.length;
int a[]= height.clone();
//前缀和
for(int i=1;i<len;i++){
a[i]=a[i]+a[i-1];
}
int res=0;
/* 遍历
for(int i=0;i<len-2;i++){
int top=-1;
int flag=0;
for(int j=i+1;j<len;j++){
if(top==-1||height[j]>height[top]){
top=j;
}
if(height[i]<=height[j]){
res+=(Math.min(height[i],height[j])*(j-i-1)-(a[j-1]-a[i]));
i=j-1;
flag=1;
break;
}
}
if(flag==0){
res+=Math.min(height[i],height[top])*(top-i-1)-(a[top-1]-a[i]);
i=top-1;
}
}
*/
int first=0,second=1;
int top=1;
while (first<=len-2&&second<len){
//记录寻找过程中的最高点，以免所有后续点都比当前点低
if(height[second]>=height[top]){
top=second;
}
//寻找first点右侧的第一个高于first的点second
if(height[second]>=height[first]){
res+=height[first]*(second-first-1)-(a[second-1]-a[first]);
first=second;
top=first+1;
}
second++;
//如果没找到，则用最高点代替
if(second==len){
if(first<len-2&&first<top){
res+= Math.min(height[first],height[top])*(top-first-1)-(a[top-1]-a[first]);
first=top;
second=first+1;
top=second;
}
}
}
return res;
}
}
大佬解法O（n）思路清晰新颖，与官方的双指针解法有异曲同工之妙
class Solution {
public:
int trap(vector<int>& height) {
int maxHeight = 0;
int maxHeightPos = -1;
for (int i=0;i<height.size();i++) {
if (height[i] > maxHeight) {
maxHeight = height[i];
maxHeightPos = i;
}
}
if (maxHeightPos == -1) return 0;
int waterHeight = 0;
int waterSum = 0;
for (int i=0;i<maxHeightPos;i++) {
// 左侧水位
if (height[i] > waterHeight) waterHeight = height[i];
waterSum += waterHeight - height[i];
}
waterHeight = 0;
for (int i=height.size()-1;i>maxHeightPos;i--) {
// 右侧水位
if (height[i] > waterHeight) waterHeight = height[i];
waterSum += waterHeight - height[i];
}
return waterSum;
}
};
官方解法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 ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
官方解法二，单调栈，时空复杂度与解法一相近，但思维难度高一点。
class Solution {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
int n = height.length;
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
int left = stack.peek();
int currWidth = i - left - 1;
int currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stack.push(i);
}
return ans;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
官方解法三，双指针，虽然时空复杂度达到了最优，但思维难度最高，很难想到，看官方题解都需要理解一段时间（大佬除外）
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
思路
首先我们观察这道题，数据量并不高，就算是O（N2）时间复杂度也能勉强通过，再构思处理思路，发现，内层遍历绝大数情况都远小于数组长度，除极端情况外，实际时间复杂度会远小于O（N2）。所以博主给出的第一份代码，就是未经过任何优化，采用O（N2）,遍历每个点右侧第一个高于自己的点，求这段距离的储水量。思路简单，想到找第一个高于自己的点也不算难，对于只想通过题目是不二之选。
但是，既然做leetcode题了，面试官怎么会管你实际复杂度小于O（N2）,他们关注的就是你的方法最差情况的时间复杂度，所以不要学不爱动脑的博主，我们肯定是需要研究更优的方法的。
解法二
首先我想讲的思路是leetcode中某位路人大佬的思路，大佬的思路是先确定最高的柱子，那么在最高的柱子左侧，所有水柱，一定是从左到右递增的，为什么，如图
因为已经确定了最高柱，那么确定水位高度的永远是从做到右的次高柱，我们从左到右遍历，遍历中的临时最高柱的高度永远会比最高柱低，那么临时最高柱的高度就是实际水位高度，右侧比他小的柱子的高度并不能影响这片水位的高度，导致随着从左到右的遍历，水位高度永远随着遍历过程中的临时最高柱增长。右侧同理。
那么，我们在确定最高柱后，只需要分别从两侧遍历一次，记录临时最高柱，然后就能计算到总储水量。
思维很巧妙，但也有一定思维难度，大家可以借鉴学习。
解法三
解法三是我最推荐的，最符合大众的解法，因为他思路简单，时空复杂度也满足要求。这个解法的着眼点在于优化遍历。我们普通遍历时间复杂度回到O（N2）级别，如何优化，可以用动态规划的思想。
动态规划思想的基础很简单，自底向上，通过底部的结果方便顶部结果的计算，从而达到减少时间复杂度，减少重复计算的目的。这道题搞好满足，我们都知道，假如每个点左侧的最大高度l，右侧的最大高度r，那么该点的储水量就是Math.min（l,r）-heigh[i]。而每个点的左侧最大高度l，又可以拆分为，math（height[i-1]，与l[i-1]）。这就是我们动态规划的状态转移方程，依照这个思路，就能以O（N）的时间复杂度完成计算每个点左侧的最大高度。右侧同理。
之后的遍历计算就不用我说明了。
解法四
单调栈的思路也同样不难，但与之前的思路都有点不一样，不常用单调栈或者不熟悉的朋友可能想不到单调栈，我们从左到右维持递减的单调栈。如果此时遍历到了i，i的高度大于i-1，由于单调栈我们知道，i-2的高度也是大于i-1的,那么当前遍历进度下，i-1这个点的储水量我们就能计算出了（注注意，计算水位高度要减去i-1的高度，因为这种方法计算的并不是这个点最终水位高度，i-1高度的水之前就可能计算过，如图），然后将计算过的点弹出，同时根据新进入的点i维持单调栈，遍历一遍即可。
解法五
思路最难的一种解法，如果让博主讲清楚的话，表达能力差的博主可能要写很多很多（很有自知之明），博主现在这里主要是对官方讲解的解释，因为官网讲的也很模糊，博主的讲解只是为了方便大家理解官方的讲解。
官方的意思是，维持左右指针，就能替换动态规划中的数组，从而节约空间，为什么能替换，只字未提。博主主要讲解这里。
首先应用官方对双指针操作的描述
维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，初始时
left=0,right=n−1,leftMax=0,rightMax=0。指针 left 只会向右移动，指针 right
只会向左移动，在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。当两个指针没有相遇时，进行如下操作：
使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；
如果 height[left]<height[right]，则必有 leftMax<rightMax，下标 left 处能接的雨水量等于
leftMax−height[left]，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）；如果 height[left]≥height[right]，则必有 leftMax≥rightMax，下标 right 处能接的雨水量等于
rightMax−height[right]，将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减
1（即向左移动一位）。当两个指针相遇时，即可得到能接的雨水总量。
作者：力扣官方题解
链接：https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
首先为了大家理解，大家可以先看对解法二的讲解，借用解法二的思路，当height[left]<height[right]，也就是右侧点高度大于左侧点高度时，从左遍历，遍历点的储水量就是左侧临时最高点-hight[i]（解法二中有讲，虽然right不是最高柱，左右指针两个点的角度来看时，右指针高度大，他就是最高柱，这也是为什么左指针小于右指针时，我们处理左边而不是右边）。其他情况同理。
简单来说左右指针，哪边高，就将哪边当为最高柱，再根据我解法二的思路，就能求得该点的储水量。十分巧妙，实际算法是与解法二如出一辙的，只是解法二的思路更容易想到，实现也更简单。
这道题实在废了博主很多心思，其实昨天就再leetcode做出来了，奈何完全弄懂所有方法并且编写博客实在耗时，博主平时也有其他事，导致没能及时发出来。但就算如此，写博客是博主巩固自己知识的过程，博主不想草草了事，大家共勉。