LeetCode 11 Container With Most Water(分支​判断问题)

 
Problem: 已知n条垂直于x轴的线段,选择其中两条,使得该线段和x轴能够存储最大量的水。
 
1、首先如何计算存储水量 横坐标之差乘以最低高度
2、遍历所有情况则需要n*(n-1)/2,时间复杂度为o(n^2)
3、根据木桶原理,容水量由最短木板决定,因此在遍历时,按照最短木板原理进行对i,j线段的选择
 
参考代码:
package leetcode_50;

/***
*
* @author pengfei_zheng
* 最大容水量问题
*/
public class Solution11 {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;//初始化最大容水量为0 while (left < right) {//遍历
maxArea = Math.max(maxArea, Math.min(height[left], height[right])
* (right - left));//更新最大容水量
if (height[left] < height[right])//当左边高度低于右边高度时,left++
left++;
else
right--;
}
return maxArea;
}
}
上一篇:535,剑指 Offer-扑克牌中的顺子


下一篇:GitHub:TensorFlow、PyTorch最全资料集锦