原题为：
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
题目大概意思为有一个非负整数的数组，代表一个柱状图，这个柱状图里每柱的宽都为1，计算下雨后这个柱状图能乘多少水？
首先找出边界条件，容易发现要想能盛水，必须在两个相邻边界（距离可以1，也可以大于1）柱子之间存在凹下去的空隙，即数组至少要有三个元素。
然后判定一般条件，凹下的空隙盛水的多少取决于相邻两个柱子中高度低的那个。使用两个指针从左右同时开始向中间扫描，找出盛水的边界。
public class Solution { public int trap(int[] A) { if (A.length < 3) return 0; int res = 0; int l = 0, r = A.length - 1; // 找出可以盛水的边界 while (l < r && A[l] <= A[l + 1]) l++; while (l < r && A[r] <= A[r - 1]) r--; while (l < r) { int left = A[l]; int right = A[r]; if (left <= right) { while (l < r && left >= A[++l]) { res += left - A[l]; } } else { while (l < r && A[--r] <= right) { res += right - A[r]; } } } return res; } }
转载于:https://www.cnblogs.com/huntertoung/p/4730636.html
相关资源：DirectX修复工具V4.0增强版