问题1
盛水最多的容器
原理
- 首先想到最多的容器肯定是：Min(两个柱子)*(柱子之间间距)
- 遍历一次需要找到最多的容器，应该采用双指针算法，并且使用max作为临时变量记录下来
代码
class Solution {
public int maxArea(int[] arr) {
if(arr==null||arr.length<=0){
return 0;
}
int max = Integer.MIN_VALUE;
int low = 0;
int high = arr.length-1;
while(low<high){
int cur = Math.min(arr[low],arr[high]);
max = Math.max(max,cur*(high-low));
if(arr[low]<arr[high]){
low++;
}else{
high--;
}
}
return max;
}
}
注意事项
- 注意联想到双指针就能cover住
问题2
接雨水的总和最大
原理
- 处理这个问题还是需要使用双指针
- 雨水的最大值应该是min(Math.max(height[left],leftMax),Math.max(height[right],rightMax)) 简单解释就是左边最大值和右边最大值，之后的最小值决定了两边围栏的高度。当前实际的蓄水量减去当前值就OK了。
代码
class Solution {
public int trap(int[] arr) {
if(arr==null||arr.length<=0){
return 0;
}
int max = 0;
int low = 0;
int high = arr.length-1;
int leftmax = arr[0];
int rightmax = arr[arr.length-1];
while(low<high){
leftmax = Math.max(leftmax,arr[low]);
rightmax = Math.max(rightmax,arr[high]);
if(arr[low]<arr[high]){
max += Math.min(leftmax,rightmax)-arr[low];
low++;
}else{
max += Math.min(leftmax,rightmax)-arr[high];
high--;
}
}
return max;
}
}
注意事项
- 注意雨水存储实际上一个一个比较计算出来的。
- 解决问题的关键在于min(Math.max(height[left],leftMax),Math.max(height[right],rightMax))- min(height[low],height[high]);
问题3
柱状图中最大的矩形
原理
代码
