杭州建设网站职称人才工作专题互联网营销师课程

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

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

class Solution {public int trap(int[] height) {//定义水块和int sum=0;Stack<Integer> stack=new Stack<>();int current=0;while(current<height.length){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 !