hot100：07接雨水

题目链接：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

算法思想：

这里采取的是暴力解法和双指针的解法，但是这个题目还有其他的两种解法（单调栈和动态规划，同学可以自行了解）

首先，在说算法思想之前，我们需要搞懂题目的意思，什么样情况属于可以接到雨水，如何相加，下面看一幅图来了解一下：

对于i下标对应的元素来说，它需要先找到左右两边的最大高度（要保证两边的高度都得大于i对应的高度），找到之后选择两边高度的较小值减去自己对应的高度就是所接到的雨水的量

暴力解法：

遍历整个数组，统计每个元素接到的雨水量进行相加（注意数组的遍历可以从1下标开始，因为0下标肯定是接不到雨水的）

//暴力解法public int trap(int[] height) {int n = height.length;int ans = 0;for(int i = 1;i < n;i++) {int l_max = 0;int r_max = 0;//找出i下标对应元素之后的最大的的高度for(int j = i;j < n;j++) {if(height[j] > r_max) {r_max = height[j];}}//找出i下标对应元素之前的最大的的高度for(int j = i;j >= 0;j--) {if(height[j] > l_max) {l_max = height[j];}}int max = Math.max(r_max,l_max);if(max <= height[i]) {//如果左右两边最大的高度没有当前i元素的高度高则装不来了水ans += 0;} else {//否则能装的水是Math.min(r_max,l_max) - height[i];ans += Math.min(r_max,l_max) - height[i];}}return ans;}

双指针解法：

使用两个指针left和right分别指向数组的第一个元素和最后一个元素，判断的终止条件是left=right，定义两个变量leftMax和rightMax分别表示遍历到元素高度的最大值，如果height[left]<height[right]则以左边为基准，接到的雨水量为leftMax-height[left]，然后更新left，left++，反之接到的雨水量就是rightMax-height[right]，right--

//双指针解法public int trap(int[] height) {int left = 0;int right = height.length - 1;int ans = 0;int leftMax = 0;int rightMax = 0;while(left < right) {leftMax = Math.max(leftMax,height[left]);rightMax = Math.max(rightMax,height[right]);if(height[left] < height[right]) {ans += leftMax - height[left];left++;} else {ans += rightMax - height[right];right--;}}return ans;}