首页 > 其他 > 详细

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

时间:2017-03-03 22:25:29      阅读:222      评论:0      收藏:0      [点我收藏+]

 
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;
    }
}

 

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

原文:http://www.cnblogs.com/zpfbuaa/p/6498563.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!