给定一个整形数组arr,已知其中所有的值都是非负的,将这个数组看作一个容器,请返回容器能装多少水
容器盛水问题
http://www.nowcoder.com/questionTerminal/31c1aed01b394f0b8b7734de0324e00f
很多人是没有理解题目,下面是别人的代码
问题的关键是找到最小边界。
如图
import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { // write code here //定义一个用来累加的变量 long count = 0L; //定义起始的左边界 int from = 0; //定义一个起始的右边界 int to = arr.length - 1; while(from < to){ //找到最小的边界 int min = Math.min(arr[from], arr[to]); //如果左边界最小则从左向右移动,并且计算容量 while(from < to && arr[from] <= min){ count += min - arr[from]; from ++; } //如果右边界最小则从右向左移动,并且计算容量 while(from < to && arr[to] <= min){ count += min - arr[to]; to --; } } return count; } }