接雨水

题目分析

给定一组柱子高度的数组 height，需要计算这些柱子之间能够接住的雨水总量。直观来看，每个柱子上方能够存多少雨水，取决于其左右两侧的最高柱子的高度。

解题思路

本题可以使用 双指针法 进行求解，主要思路如下：

1. 维护两个指针 left 和 right，分别指向数组的左右两端。
2. 维护两个变量 left_max 和 right_max，分别表示当前位置左侧和右侧的最大高度。
3. 如果 height[left] < height[right]，说明 left 侧的最大值决定了 left 位置能接多少水：

Leetcode 7.接雨水-原题链接

题目内容

给定$n$个非负整数表示每个宽度为 $1$的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入描述

输入共两行。

• 第一行为两个个整数$n$，代表数组$height$的长度。

• 第二行为$n$个整数$height_0,height_1,...,height_{n-1}$，数字之间以空格分隔。

输出描述

一个整数，表示答案。

样例1

输入

12
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

输入

6
4 2 0 3 2 5

输出

9

提示

• $n == height.length$
• $1 <= n <= 2 * 10^4$
• $0 <= height[i] <= 10^5$