做徽章的网站,顺企网查企业电话,网站建设服务好的商家,做uml图网站题意理解#xff1a; 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 左边的柱子和右边的柱子形成围栏#xff0c;可以使中间能够积水 求最大的积水面积。h*w 解题思路#xff1a; 1.横向求解 这里的单… 题意理解 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 左边的柱子和右边的柱子形成围栏可以使中间能够积水 求最大的积水面积。h*w 解题思路 1.横向求解 这里的单调栈采用的是横向求解。 求最右变第一个比他大的值作为右边界栈顶第一个元素lpop()作为底座下下一个栈顶元素peek()作为左边界 则最高高度min(height[i], height[peek()]) 则积水面积高度最高高度-底座min(height[i], height[peek()])-l 积水的宽度i-peek()-1 积水面积h*w(min(height[i], height[peek()])-l) * (i-peek()-1) 当且仅当stack有2个及以上元素时进行如上操作 若元素小于2此时未形成积水面积则pop()无法积水的高度元素 2.纵向求解 1.单调栈解题
public int trap(int[] height) {int result0;StackInteger stacknew Stack();stack.push(0);for(int i1;iheight.length;i){if(height[i]height[stack.peek()]){stack.push(i);}else{while((!stack.isEmpty())height[i]height[stack.peek()]){if(stack.size()2){int midstack.pop();int hMath.min(height[i],height[stack.peek()])-height[mid];int wi-stack.peek()-1;resultw*h;}else{stack.pop();}}stack.push(i);}}return result;}
2.复杂度分析 时间复杂度O(n^2) 空间复杂度O(1)
