描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
链接
42. 接雨水 - 力扣（LeetCode） (leetcode-cn.com)
解法一：双指针
1 class Solution {
2 // 总体思想，一格一格的去计算
3 public int trap(int[] height) {
4 int left = 0, right = height.length - 1;
5 int ans = 0;
6 // 存放左右两侧的 最大值
7 int left_max = 0, right_max = 0;
8
9 //遍历
10 while (left < right) {
11 // 总体上，谁低，就决定了 最多能 接的雨水量，所以先 判断 左右 谁大
12
13 // 左小，那么 左决定
14 if (height[left] < height[right]) {
15
16 // 只有当 接下来的小于 左侧最大值，才能计算
17 if (height[left] >= left_max) {
18 left_max = height[left];
19 } else {
20 ans += (left_max - height[left]);
21 }
22 ++left;
23 }
24
25 // 右小，那么 右决定
26 else {
27 // 只有当 接下来的小于 右侧最大值，才能计算
28 if (height[right] >= right_max) {
29 right_max = height[right];
30 } else {
31 ans += (right_max - height[right]);
32 }
33 --right;
34 }
35 }
36 return ans;
37 }
38 }
解法二：用栈
1 class Solution {
2 public int trap(int[] height) {
3 if (height.length < 2) return 0;
4 Stack<Integer> stack = new Stack<>();
5 // 开始时，水的面试是0
6 int res = 0;
7
8 // 开始遍历
9 for (int i = 0; i < height.length; i++) {
10 // 如果栈为空，那么直接把当前索引加入到栈中
11 if (stack.isEmpty()) {
12 stack.push(i);
13 }
14 // 否则的话，栈里面是有值的，我们需要去判断此时的元素、栈顶元素、栈顶之前的元素能否形成一个凹槽
15 // 情况一：此时的元素小于栈顶元素，凹槽的右侧不存在，无法形成凹槽
16 else if (height[i] < height[stack.peek()]) {
17 // 继续添加
18 stack.push(i);
19 }
20 // 情况二：此时的元素等于栈顶元素，也是无法形成凹槽
21 else if (height[i] == height[stack.peek()]) {
22 stack.push(i);
23 }
24 // 情况三：此时的的元素大于栈顶元素，有可能形成凹槽
25 // 注意是有可能形成，因为比如栈中的元素是 2 、2 ，此时的元素是 3，那么是无法形成凹槽的
26 else {
27 // 由于栈中有可能存在多个元素，移除栈顶元素之后，剩下的元素和此时的元素也有可能形成凹槽
28 // 因此，我们需要不断的比较此时的元素和栈顶元素
29 // 此时的元素依旧大于栈顶元素时，我们去计算此时的凹槽面积
30 // 借助 while 循环来实现这个操作
31 while (!stack.empty() && height[i] > height[stack.peek()]) {
32
33 // 1、获取栈顶的下标，bottom 为凹槽的底部位置
34 int bottom = stack.peek();
35
36 // 将栈顶元素推出，去判断栈顶之前的元素是否存在，即凹槽的左侧是否存在
37 stack.pop();
38
39 // 2、如果栈不为空，即栈中有元素，即凹槽的左侧存在
40 if (!stack.empty()) {
41
42 // 凹槽左侧的高度 height[stack.peek() 和 凹槽右侧的高度 height[i]
43 // 这两者的最小值减去凹槽底部的高度就是凹槽的高度
44 int h = Math.min(height[stack.peek()], height[i]) - height[bottom];
45
46 // 凹槽的宽度等于凹槽右侧的下标值 i 减去凹槽左侧的下标值 stack.peek 再减去 1
47 int w = i - stack.peek() - 1;
48
49 System.out.println("凹槽右侧-->" + i);
50 System.out.println("凹槽左侧-->" + stack.peek());
51 System.out.println("凹槽高度-->" + h);
52 System.out.println("凹槽宽度-->" + w);
53 System.out.println("凹槽面积-->" + h * w);
54 System.out.println("---------------");
55
56 // 将计算的结果累加到最终的结果上去
57 res += h * w;
58 }
59 }
60
61 // 栈中和此时的元素可以形成栈的情况在上述 while 循环中都已经判断了
62 // 那么，此时栈中的元素必然不可能大于此时的元素，所以可以把此时的元素添加到栈中
63 stack.push(i);
64 }
65 }
66 return res;
67 }
68 }
题解链接
1、「代码随想录」带你搞定单调栈！ 42. 接雨水:【双指针】【动态规划】【单调栈】详解！ - 接雨水 - 力扣（LeetCode） (leetcode-cn.com)
2、接雨水（ LeetCode 42 ）_AlgoMooc算法慕课网