首页 > 代码库 > 算法实现柱形集合积水面积
算法实现柱形集合积水面积
用一个数组代表柱形墙的的高度。当下雨的时候柱形墙能积水的体积是多少
下面是python的实现算法：
# -*- coding: utf-8 -*-def savewater(arr): point_l=0 max_l=arr[0] point_r=len(arr)-1 max_r=arr[len(arr)-1] volume=0 #point_l从左向右遍历,point_r从右向左遍历 while point_l<point_r: #能积水的标准时两边的高度大于中间的 if max_l<max_r: point_l=point_l+1 if max_l<=arr[point_l]: max_l=arr[point_l] else: volume=volume+max_l-arr[point_l] else: point_r=point_r-1 if max_r<=arr[point_r]: max_r=arr[point_r] else: volume=volume+max_r-arr[point_r] return volume if __name__==‘__main__‘: arr=[1,2,3,4,2,1,1,5,3,2] volume=savewater(arr) print volume
java实现算法：
package com.gh.d1;/** * Created by Lenovo on 2014/12/29. */public class D1_1 { public static void main(String[] args){ int[] array=new int[]{1,2,3,4,2,1,1,5,3,2}; int volume=savewater(array); System.out.println(volume); } public static int savewater(int[] array) { int point_l = 0; int max_l = 0; int point_r = array.length; int max_r = array[array.length - 1]; int volume = 0; while (point_l < point_r) { if (max_l < max_r) { point_l++; if (max_l <= array[point_l]) { max_l = array[point_l]; } else { volume = volume + max_l - array[point_l]; } } else { point_r--; if (max_r <= array[point_r]) { max_r = array[point_r]; } else { volume = volume + max_r - array[point_r]; } } } return volume; }}
golang实现：
package mainimport ( "fmt")func main() { arr := []int{1, 2, 3, 4, 2, 1, 1, 5, 3, 2} volume := savewater(arr) fmt.Println(volume)}func savewater(arr []int) int { point_l := 0 max_l := 0 point_r := len(arr) - 1 max_r := arr[len(arr)-1] volume := 0 for point_l < point_r { if max_l < max_r { point_l++ if max_l < arr[point_l] { max_l = arr[point_l] } else { volume = volume + max_l - arr[point_l] } } else { point_r-- if max_r < arr[point_r] { max_r = arr[point_r] } else { volume = volume + max_r - arr[point_r] } } } return volume}
算法实现柱形集合积水面积
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。