存水
给定一个数组,看做容器,求可以存储的水的体积
Arr = {3,1,3} à 可以存2
Arr = {1,2,3,4,2,1} à 可以存1
算法解析:
- 以单个元素来看,位于其顶部的水的体积为左右两侧最大值集合中的最小一项减去其位置的高度的值,对其所有元素进行计算即可求出
- 左右两侧设置最大值,从头尾开始遍历,设定leftMax与rightMax, 若是leftMax<rightMax,说明右侧元素是否可以存水及存多少看左边的值(木桶原理),反之亦然
public int getWater1(int[] arr){
int val = 0;
int leftMax = arr[0];
int rightMax = arr[arr.length-1];
int leftIndex = 1;
int rightIndex = arr.length-2;
while(leftIndex<=rightIndex){ //此处需要注意是 <=
if(leftMax>rightMax){ //注意leftMax>rightMax时,需要比较与修改的是rightIndex
val += Math.max(0, leftMax-arr[rightIndex]);
rightMax = Math.max(rightMax, arr[rightIndex--]);
}else{
val += Math.max(0, rightMax-arr[leftIndex]);
leftMax = Math.max(leftMax, arr[leftIndex++]);
}
}
return val;
}
柱子间最大面积
给定一个数组,看做每个元素为柱子高度,宽度默认为1
求其两根柱子间可以围出的最大面积
Arr = {3,1,2,4} à 3*2 = 6
算法解析:
- 左右两侧开始遍历,较小的会影响所求的面积
public int getArea(int[] arr){
int max;
int leftIndex = 0;
int rightIndex = arr.length-1;
max = Math.min(arr[leftIndex],arr[rightIndex])*(rightIndex-leftIndex-1);
while(leftIndex<rightIndex){
if(arr[leftIndex]<arr[rightIndex]){
max = Math.max(max,
Math.min(arr[++leftIndex], arr[rightIndex])*(rightIndex-leftIndex-1));
}else{
max = Math.max(max,
Math.min(arr[--rightIndex],arr[rightIndex])*(rightIndex-leftIndex-1));
}
}
return max;
}
