Trapping rain water

此题的第一问就是一个一维双指针对撞型题，解题关键在于知道每一段水沟只取决于两侧的木板，放到双指针的思想里则是任意从左侧或者右侧开始扫描，直到扫到一根柱子的高度比开始的那个柱子还要高然后停止，把中间的这段累积数加起来就是最后结果了，下面是第一问的代码

public class Solution {
    public int trap(int[] height) {
        int start = 0;
        int end = height.length - 1;
        int result = 0;

        while (start < end && height[start] == 0) {
            start++;
        }

        while (start < end && height[end] == 0) {
            end--;
        }

        while (start < end) {
            if (height[start] < height[end]) {
                int tmp = height[start];
                start++;
                while (start < end && tmp > height[start]) {
                    result += (tmp - height[start]);
                    start++;
                }
            } else {
                int tmp = height[end];
                end--;
                while (start < end && tmp > height[end]) {
                    result += (tmp - height[end]);
                    end--;
                }
            }
        }

        return result;
    }
}

Python代码

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        start, end = 0, len(height) - 1
        while start < end:
            if height[start] != 0:
                break
            start += 1

        while start < end:
            if height[end] != 0:
                break
            end -= 1

        res = 0
        while start < end:
            if height[start] < height[end]:
                tmp = height[start]
                start += 1
                while tmp > height[start]:
                    res += (tmp - height[start])
                    start += 1
            else:
                tmp = height[end]
                end -= 1
                while tmp > height[end]:
                    res += (tmp - height[end])
                    end -= 1
        return res

上面的双指针算法是此题的最优解，时间复杂度O(n)，空间复杂度O(1)，但是这道题也可以用其他解法，暴力的O(n^2)时间复杂度也是可以过的，算法也很简单，对于每一个非边界点，我们逐个从它的左边和右边扫描找出最高的那块板子，然后取左右最高的板与这块板本身相减得到的就是这个位置能装下的水了，下面是代码

public class Solution {
    public int trap(int[] height) {
        int res = 0;
        int n = height.length;

        for (int i = 1; i < n - 1; i++) {
            int left = 0;
            int right = 0;
            for (int l = i; l >= 0; l--) {
                left = Math.max(left, height[l]);
            }

            for (int r = i; r < n; r++) {
                right = Math.max(right, height[r]);
            }

            res += (Math.min(left, right) - height[i]);
        }

        return res;
    }
}

然后根据上面这个暴力版本，可以明显发现我们要求每一个位置左边和右边的最大值，所以我们可以利用动态规划建立两个数组，一个记录左边的最大值，一个记录右边的最大值，然后再对每个位置求装水量就行了，这样时间复杂度就下降到了O(n)

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)

        dp_left = [0] * n
        dp_left[0] = height[0]
        for i in xrange(1, n):
            dp_left[i] = max(dp_left[i - 1], height[i])

        dp_right = [0] * n
        dp_right[n - 1] = height[-1]
        for i in xrange(n - 1, -1, -1):
            dp_right[i] = max(dp_right[i + 1], height[i])

        res = 0
        for i in xrange(n):
            res += (min(dp_left[i], dp_right[i]) - height[i])
        return res

还有一种stack的方法，实在对栈的解法都觉得不好理解，以后有空再研究

最后是单调栈的方法，这个方法是通过维护单调递减栈来求得结果的，首先每一次遇到一块高板，我们把里面所有低于它的板全部弹出，每次弹出的时候取弹出后的栈顶板高和当前板高的最小值（为什么要这么做？思考4，2，3这个输入）减去弹出的板高，每一次这样做，相当于我们用水泥把这两块板中间的坑抹平了，这样就保证了单调栈的结果正确性

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        stack = []
        result = 0
        for index, h in enumerate(height):
            if not stack or stack[-1][0] >= h:
                stack.append((h, index,))
                continue

            while stack and stack[-1][0] < h:
                tmp = stack.pop()
                if stack:
                    result += (min(stack[-1][0], h) - tmp[0]) * (index - stack[-1][1] - 1)
                else:
                    break
            stack.append((h, index, ))

        return result