网站怎么进入后台维护,同时部署WordPress和django,公司网站建设制作难么,做企业网站一般要多少钱题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 输入输出示例 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出#xff1a;6 解释#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1… 题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 输入输出示例 输入height [0,1,0,2,1,0,1,3,2,1,2,1] 输出6 解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水 解决方案
基本思想
1.初始化 ans 0。
2.从左到右遍历 height:
初始化 left_max 0,right max 0。
从 height[0]到当前位置寻找最大值left_max max(height[j]left_max)。
从当前位置到 height 末端寻找最大值right max max(height[j]right max)。
ans ans min(left max,right max)-height[i]。
方式一动态规划
算法思路提前储存每个位置上所有左边柱子高度的最大值和所有右边柱子高度的最大值 我们可以看到重叠部分就是left_max[i]和right_max[i]之间的最小值如果要获取存水量需要和当前的高度做差 实现代码
class Solution {public int trap(int[] height) {int ans0;//定义结果集int lenheight.length;if(len3){return 0;//这种情况下存不住水}int[] left_maxnew int[len];//每个位置上所有左边柱子高度的最大值int[] right_maxnew int[len];//每个位置上所有右边柱子高度的最大值left_max[0]height[0];right_max[len-1]height[len-1];for(int i1;ilen;i){left_max[i]Math.max(left_max[i-1],height[i]);}for(int ilen-2;i0;i--){right_max[i]Math.max(right_max[i1],height[i]);}for(int i0;ilen;i){ansMath.min(left_max[i],right_max[i])-height[i];//left_max[i]和right_max[i]之间的最小值如果要获取存水量需要和当前的高度做差}return ans;}
}
复杂度分析
时间复杂度O(n)
其中 n 是数组 height 的长度。计算数组 leftMax 和 rightMax 的元素值各需要遍历数组 height 一次计算能接的雨水总量还需要遍历一次。
空间复杂度O(n)
其中 n 是数组 height 的长度。需要创建两个长度为 n 的数组 leftMax 和 rightMax。
方式二单调栈
算法思想积水只能在低洼处形成当后面的柱子高度比前面的低时是无法接雨水的。所以使用单调递减栈储存可能储水的柱子当找到一根比前面高的柱子就可以计算接到的雨水。
实现步骤
使用栈 st 来存储柱子的索引下标。从左到右遍历 height:当栈非空目 height[i] height[st.peek()]。意味着栈中元素可以被弹出弹出栈顶元素。topst.pop()计算积水宽度即当前元素和栈顶元素的距离准备进行填充操作。distancei-st.peek()-1找出积水高度。water_height min(height[i],height[st.peek()])- height[top]往答案中累加积水量。ans distance *bounded_height将当前索引下标入栈。将 i移动到下个位置。
实现代码
class Solution {public int trap(int[] height) {StackInteger stnew StackInteger();//使用栈 st 来存储柱子的索引下标。int i0,ans0;while(iheight.length){while(!st.empty()height[i]height[st.peek()]){int topst.pop();//if(st.empty()) break;int widthi-st.peek()-1;int water_heightMath.min(height[i],height[st.peek()])-height[top];answidth*water_height;}st.push(i);}return ans;}
} 取出栈顶元素因为是单调递减栈所以之前的元素比栈顶元素高当前元素也比栈顶元素高因此在栈顶元素top会形成低洼 我们可以求出现在的存水量
求宽度 当前元素为低洼地区的右边界而此时的栈顶元素为低洼的左边界因而可以求出低洼处的宽度
求高度 高度应为两个边界高度的较小值减去低洼处的高度
求面积 方法三: 双指针
算法思想
从动态规划方法的示意图中我们注意到只要 left_max[i]right_max[i]积水的高度将由
right_max决定同理如果 right_max[i]left_max[i]积水的高度将由left_max决定
所以我们可以认为如果右端有更高的条形块积水的高度依赖于当前方向的高度(从左到
右)即左边这些柱子的高度决定。当我们发现左侧有更高的条形块我们则开始从相反的方向遍历(从右到左)即积水的高度由右边这些柱子的高度决定。 实现步骤
初始化两个指针left0和right height.length - 1。
当 left right 时向中间移动两个指针:
如果 height [left] height[right]说明储水量依赖于 height[left]的高度(可能构成低洼的右边界很大) 如果 height[left] left max 说明没有或超出左边边界不构成低洼left max height[left]。如果 height[left]前进 left。left 如果 height[left] height[right]说明储水量依赖于 height[right]的高度(可能构成低洼的左边界很大) 如果 height[right] right max说明没有或超出右边边界不构成低洼right max height[right]如果 height[right]height[right]前进 right。right --
实现代码
class Solution {public int trap(int[] height) {int left0,rightheight.length-1;int left_max0,right_max0,ans0;while(leftright){if(height[left]height[right]){//高的在右边正向遍历找存储的if(height[left]left_max){left_maxheight[left];}else{ansleft_max-height[left];}left;}else{if(height[right]right_max){right_maxheight[right];//更新右侧最高点}else{ansright_max-height[right];}right--;}}return ans;}
}
复杂度分析
时间复杂度O(n)
其中 n 是数组 height 的长度。两个指针的移动总次数不超过 n。
空间复杂度O(1)
只需要使用常数的额外空间。
