leetcode42——接雨水——java实现

题目要求：

按照我们定义滑动指针的惯例，我们首先定义两个指针left和right，分别指向height数组下标为0和height.length - 1处，再对height数组进行遍历。如果height[left]的值小于等于height[right]，我们就令left ++，否则，就令right --。

以上说的都是一种定势思维，即一说到滑动指针就要条件反射地想到要类似于这样处理。那么，在这样处理了之后，我们应该如何取到我们想要的蓄水面积呢？

分析如下：
我们定义两个max，分别来记录左指针left和右指针right所走过的最大值，分别将它们记为left_max和right_max，然后：

好了，故事到这里就结束了，我们可以从上面的分析来写代码了。

具体代码如下:

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int left_max = 0, right_max = 0;
        int area = 0;
        
        while(left <= right) {
            if(height[left] <= height[right]) {
                left_max = (height[left] > left_max) ? height[left] : left_max;
                if(height[left] < left_max) {
                    area = area + left_max - height[left];
                }
                left ++;
            } else {
                right_max = (height[right] > right_max) ? height[right] : right_max;
                if(height[right] < right_max) {
                    area = area + right_max - height[right];
                }
                right --;
            }
        }
        return area;
    }
}

我们可以看到，当分析完之后，代码写起来将会十分简单。
这道题的难易程度是“困难”，它的困难主要是它思考的方向以及分析的过程，一旦解决了分析过程之后，接下来的事情就会变得很简单。