有个做h手游的网站,抖音代运营合作,做网站沧州,手机百度搜索引擎入口题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图#xff0c;在这种情况下#xff0c;可以接 6 个单位的雨水#xff08;蓝色部分表示…题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 61、 暴力法
/***接雨水暴力解法* 对于数组中的每个元素我们找出下雨后水能达到的最高位置等于两边最大高度的较小值减去当前高度的值。* param height* return*/
public int trap(int[] height) {if(height null || height.length 2) {return 0;}int leftMax0, rightMax0;int count0;for(int i1;iheight.length-1;i) {leftMax0;rightMax0;for(int j0;ji;j) {leftMax Math.max(leftMax, height[j]);}for(int jheight.length-1; ji;j--) {rightMax Math.max(rightMax, height[j]);}if(leftMax0 rightMax0 Math.min(leftMax, rightMax)height[i]) {count(Math.min(leftMax, rightMax) - height[i]);}}return count;}2、空间换时间
/***接雨水* 用空间换时间记录下每个节点的左侧最大值右侧最大值* 对于数组中的每个元素我们找出下雨后水能达到的最高位置等于两边最大高度的较小值减去当前高度的值。* param height* return*/
public int trap(int[] height) {if(height null || height.length 2) {return 0;}int[] leftMax new int[height.length];for(int i1;iheight.length;i) {leftMax[i] Math.max(leftMax[i-1], height[i-1]);}int[] rightMax new int[height.length];for(int iheight.length-2;i0;i--) {rightMax[i] Math.max(rightMax[i1], height[i1]);}int count0;for(int i1;iheight.length-1;i) {if(Math.min(leftMax[i], rightMax[i])height[i]) {count(Math.min(leftMax[i], rightMax[i])-height[i]);}}return count;}
