LeetCode第十六天栈之接雨水42多解

栈

    public static int trap(int[] height) {
        int results=0;
        Deque<Integer> stack=new ArrayDeque<>();
        for (int i=0;i<height.length;i++){
            while(!stack.isEmpty()&&height[stack.peek()]<height[i]){
                int top=stack.pop();
                if (stack.isEmpty()) break;
                int Width=i-stack.peek()-1;
                int Height=Math.min(height[i],height[stack.peek()])-height[top];
                results+=Width*Height;
            }
            stack.push(i);
        }
        return results;
    }

数学方法（思路出自leetcode上的一位数学大神）

• 从左往右遍历 s1
  

• 从右往左遍历 s2
  

• 两次遍历相加
  
  你会发现，两次遍历相加（s1+s2）包含：大矩形面积+柱子面积+雨水面积

• 代码来了

    public static int trap(int[] height) {
        int max=0,sumr=0,suml=0,zz=0,jx=0;
        int result=0;
        for (int i=0;i<height.length;i++){
            max=Math.max(max,height[i]);
            sumr+=max;
        }
        jx=max*height.length;
        max=0;
        for (int i=height.length-1;i>=0;i--){
            max=Math.max(max,height[i]);
            suml+=max;
        }
        for (int i=0;i<height.length;i++){
            zz+=height[i];
        }
        result=suml+sumr-jx-zz;
        return result;
    }

学以致用

（栈）

• 使用栈来存储柱子的索引下标
• 当栈不为空，且遇到下一个元素比栈顶元素大时
  栈顶元素出栈，且记录栈顶元素int top=stack.pop();
  计算宽度（当前元素与当前栈顶元素之间距离）int Width=i-stack.peek()-1;
  计算高度（当前元素与当前栈顶元素取较小值-被删除栈顶元素）
  int Height=Math.min(height[i],height[stack.peek()])-height[top];
  累加积水量results+=Width*Height;
• 当前索引存入栈stack.push(i);
• i往下继续移动