42. 接雨水

题意：

解题思路：

思路：
1. 双指针扫描 O(n)
    1.1 找到图中最高的矩形，然后从左至右扫描到最高点，从右到左扫描到最高点；
    1.2 从左至右扫描到最高点,如果右边矩形高度小于左边矩形高度，计算差值；
    1.3 从右到左扫描到最高点,如果左边矩形高度右边右边矩形高度，计算差值；
    1.4 最后统计总差值
2. (单调栈) O(n)
    1.1 如果要求水的面积，一定要形成一个U字形
    1.2 维护一个递减的单调栈，如果下一个i大于栈顶元素，我们pop出栈顶的元素（即凹槽的部分），再判断是否栈顶元素是否为空，如果不为空，则一定可以形成一个U字形
    1.3 计算U形面经：($i - $stack->top() - 1) * (min($height[$i], $height[$stack->top()]) - $height[$top]);
    1.4 min($height[$i], $height[$stack->top()] : 木桶原理，蓄水的面经由最短的那块板子决定
    1.5 (min($height[$i], $height[$stack->top()]) - $height[$top])：如果$height[$top]有值，必须去掉这部分值，不然面积多算了这部分值；

PHP代码实现：

class Solution {
    function trap($height) {
        $area = 0;
        $maxIdx = $this->getHeight($height);
        $leftHeight = $height[0];
        for ($i = 0; $i < $maxIdx; $i++) {
            //下一个小的话就计算面积    
            if ($leftHeight < $height[$i]) {
                $leftHeight = $height[$i];
            } else {
                $area += $leftHeight - $height[$i];
            }
        }
        $rightHeight = $height[count($height) - 1];
        for ($i = count($height) - 1; $i > $maxIdx; $i--) {
            if ($rightHeight < $height[$i]) {
                $rightHeight = $height[$i];
            } else {
                $area += $rightHeight - $height[$i];
            }
        }
        return $area;
    }
    function getHeight($height) {
        $maxV = 0;
        $maxIdx = 0;
        for ($i = 0; $i < count($height); $i++) {
            if ($height[$i] > $maxV) {
                $maxV = $height[$i];
                $maxIdx = $i;
            }
        }
        return $maxIdx;
    }
    function trapByStack($height) {
        $stack = new SplStack;
        $res = 0;
        for ($i = 0; $i < count($height); $i++) {
            if ($stack->isEmpty() || $height[$i] < $height[$stack->top()]) {
                $stack->push($i);
            } else {
                while (!$stack->isEmpty() && $height[$i] > $height[$stack->top()]) {
                    $top = $stack->pop();
                    if (!$stack->isEmpty()) {
                        $res += ($i - $stack->top() - 1) * (min($height[$i], $height[$stack->top()]) - $height[$top]);
                    }
                }
                $stack->push($i);
            }
        }
        return $res;
    }
}

GO代码实现：

func trap(height []int) int {
    if len(height) == 0 { return 0 }
    left, right, res, leftMax, rightMax := 0, len(height)-1, 0, 0, 0
    for left < right {
        if height[left] <= height[right]{
            // 左->右
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                res += leftMax - height[left]
            }
            left++
        } else {
            // 右->左
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                res += rightMax - height[right]
            }
            right--
        }
    }
    return res
}