【力扣】42. 接雨水

这道题我卡了差不多1个小时，不是不会做，是不知道怎么能用栈来实现，后面看了一个博主的视频，豁然开朗，我主要的纠结点在于当指针指到7的时候，我计算出4到7的水块是2，但实际上是0，因为用栈是横向求解的，就是你横着来切一刀就行，然后掌握其原理。

先放代码吧，看不懂再看我的题解

class Solution {
    public int trap(int[] height) {
        //定义水块和
        int sum=0;
        Stack stack=new Stack<>();
        int current=0;
        while(current
            while(!stack.empty()&&height[current]>height[stack.peek()]){
                //获得栈顶元素的高度
                int h=height[stack.peek()]; 
                stack.pop(); //出栈
                if(stack.empty()){
                    break;
                }
                //计算方式
                int dt=current-stack.peek()-1;
                int min=Math.min(height[current],height[stack.peek()]);
                sum=sum+(min-h)*dt;
            }        
            //存放的是坐标    
            stack.push(current);
            current+=1;
        }
    return sum;
  }
}

题解如下：

1.首先讲一下原理，栈，用的时候注意里面存放的是单调递增的元素，从下往上看

2.过程：

根据本题来看，首先第一个height[0]入栈，指针后移，此时指针所指向的元素大于栈顶元素，所以栈顶元素出栈。height[1]入栈，指针后移，此时指针所指向的元素小于栈顶元素，height[2]入栈指针后移，height[3]>height[2]，所以height[2]出栈 ，找到height[2]左边的比他大的元素，也就是栈顶元素。这个其实是已经排序好的，懂吧，然后比较左边和右边的元素，找出最小值，再减去之前出栈的元素的高度，再乘以左右两边元素之差-1，就是这样子，这个计算方法就是这样的，后面也就以此类推了。再见！祝各位刷题人happy !