本文共 1303 字，大约阅读时间需要 4 分钟。

1. 本题知识点

双指针

2. 题目描述

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 1:

输入:

[0,1,0,2,1,0,1,3,2,1,2,1]

输出:

6

3. 解题思路

找出最高点，分别从两边往最高点遍历:如果下一个数比当前数小，说明可以接到水

4. 代码

public class Solution {
       public int trap(int[] height) {
           int result = 0;        int maxValue = 0;        int maxIndex = 0;        // 取数组最大值及下标        for (int i = 0; i < height.length; i++) {
               if (height[i] >= maxValue) {
                   maxValue = height[i];                maxIndex = i;            }        }        // 左半部分处理        for (int left = 0; left < maxIndex; left++) {
               for (int i = left + 1; i <= maxIndex; i++) {
                   if (height[i] < height[left]) {
                       result += height[left] - height[i];                } else {
                       left = i;                }            }        }        // 右半部分处理        for (int right = height.length - 1; right > maxIndex; right--) {
               for (int i = right - 1; i >= maxIndex; i--) {
                   if (height[i] < height[right]) {
                       result += height[right] - height[i];                } else {
                       right = i;                }            }        }        return result;    }}

转载地址：http://jcjvb.baihongyu.com/