第42题---Trapping Rain Water

• 题意描述

  • 给定一个数组，数组代表高度，可以看做两个木板，向中间盛水，能盛多少水，如下图
    

• 思路一

  • 直接暴力的想法，找到数组中的最大值，分成左右俩边，找左右两边的最大值，计算水量，递归

• 思路二

  • 辅助数组（两个辅助数组，记录从左到右的最大值和从右到左的最大值）

• 思路三

  • 上面思路的从左到右的最大值可以由一个变量统计

• 思路四

  • 两个指针，两个变量记录两边的最大值，指针移动，取两个最大值的最小值的指针，向中间移动，如果大于最大值，更新最大值；小于最大值，则统计水量

    class Solution {
    public:
        int trap(vector<int>& height) {
            int size = height.size();
            if(size == 0)
                return 0;
            
            int leftmax = -1;
            int rightmax = -1;
            
            int left = 0;
            int right = size-1;
            
            int result = 0;
            
            while(left <= right) {
                if(leftmax < rightmax) {
                    if(leftmax >= height[left]) {
                        result += (leftmax - height[left]);
                    } else {
                        leftmax = height[left];
                    }
                    left ++;
                } else {
                    if(rightmax >= height[right]) {
                        result += (rightmax - height[right]);
                    } else {
                        rightmax = height[right];
                    }
                    right --;
                }
            }
            return result;
        }
    };