文章目录
1. 题目2. 解题2.1 正反扫描法2.2 双指针2.3 单调栈
1. 题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例
:
输入
: [0,1,0,2,1,0,1,3,2,1,2,1]
输出
: 6
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/trapping-rain-water 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
类似题目： LeetCode 11. 盛最多水的容器（双指针） LeetCode 84. 柱状图中最大的矩形（单调递增栈）
2.1 正反扫描法
正向扫描记录每个位置的历史最大值存入，反向亦然每个位置取上面得到的较小的值减去自身高度
class Solution {
public:
int trap(vector
<int>& h
) {
if(h
.empty())
return 0;
int i
= 0, s
= 0, n
= h
.size();
int Lmax
[n
], Rmax
[n
];
Lmax
[0] = h
[0];
for(i
= 1; i
< n
; ++i
)
Lmax
[i
] = max(h
[i
],Lmax
[i
-1]);
Rmax
[n
-1] = h
[n
-1];
for(i
= n
-2; i
>= 0; --i
)
Rmax
[i
] = max(h
[i
],Rmax
[i
+1]);
for(i
= 1; i
< n
-1; ++i
)
s
+= min(Lmax
[i
],Rmax
[i
])-h
[i
];
return s
;
}
};
2.2 双指针
class Solution {
public:
int trap(vector
<int>& h
) {
if(h
.empty())
return 0;
int l
= 0, r
= h
.size()-1, s
= 0;
int Lmax
= 0, Rmax
= 0;
while(l
< r
)
{
if(h
[l
] < h
[r
])
{
h
[l
] >= Lmax
? (Lmax
= h
[l
]) : s
+= Lmax
-h
[l
];
++l
;
}
else
{
h
[r
] >= Rmax
? (Rmax
= h
[r
]) : s
+= Rmax
-h
[r
];
--r
;
}
}
return s
;
}
};
2.3 单调栈
单调递减栈相当于维护了左边的高墙遇到当前位置大于栈顶元素，就找到右边高墙计算栈顶元素可以接水量，删除栈顶循环判断直到当前位置 <= 栈顶（不能储水）
class Solution {
public:
int trap(vector
<int>& h
) {
if(h
.empty())
return 0;
int s
= 0, top
, distance
, height
;
stack
<int> stk
;
for(int i
= 0; i
< h
.size(); ++i
)
{
while(!stk
.empty() && h
[i
] > h
[stk
.top()])
{
top
= stk
.top();
stk
.pop();
if(stk
.empty())
break;
distance
= i
-stk
.top()-1;
height
= min(h
[i
],h
[stk
.top()]) - h
[top
];
s
+= distance
*height
;
}
stk
.push(i
);
}
return s
;
}
};
