公司想做个网站,网页设计的网网页设计的网站,建设工程施工许可证查询网站,环保部网站建设项目验收方案这道题我卡了差不多1个小时#xff0c;不是不会做#xff0c;是不知道怎么能用栈来实现#xff0c;后面看了一个博主的视频#xff0c;豁然开朗#xff0c;我主要的纠结点在于当指针指到7的时候#xff0c;我计算出4到7的水块是2#xff0c;但实际上是0#xff0c;因为…这道题我卡了差不多1个小时不是不会做是不知道怎么能用栈来实现后面看了一个博主的视频豁然开朗我主要的纠结点在于当指针指到7的时候我计算出4到7的水块是2但实际上是0因为用栈是横向求解的就是你横着来切一刀就行然后掌握其原理。
先放代码吧看不懂再看我的题解
class Solution {public int trap(int[] height) {//定义水块和int sum0;StackInteger stacknew Stack();int current0;while(currentheight.length){while(!stack.empty()height[current]height[stack.peek()]){//获得栈顶元素的高度int hheight[stack.peek()]; stack.pop(); //出栈if(stack.empty()){break;}//计算方式int dtcurrent-stack.peek()-1;int minMath.min(height[current],height[stack.peek()]);sumsum(min-h)*dt;} //存放的是坐标 stack.push(current);current1;}return sum;}
}
题解如下 1.首先讲一下原理栈用的时候注意里面存放的是单调递增的元素从下往上看
2.过程
根据本题来看首先第一个height[0]入栈指针后移此时指针所指向的元素大于栈顶元素所以栈顶元素出栈。height[1]入栈指针后移此时指针所指向的元素小于栈顶元素height[2]入栈指针后移height[3]height[2]所以height[2]出栈 找到height[2]左边的比他大的元素也就是栈顶元素。这个其实是已经排序好的懂吧然后比较左边和右边的元素找出最小值再减去之前出栈的元素的高度再乘以左右两边元素之差-1就是这样子这个计算方法就是这样的后面也就以此类推了。再见祝各位刷题人happy !
