首页 > 其他 > 详细

Leetcode 11. Container With Most Water (two pointers)

时间:2018-04-22 12:29:53      阅读:163      评论:0      收藏:0      [点我收藏+]

Leetcode: 11

there are two ways to deal with two pointers

one is O(n), two pointers moves from both side

Another is O(2N), two pointer move from the same side

 

Idea for this, choose the first one and then if there is a smaller one, change that corresponding pointer until bigger that the prior bigger one.

class Solution {
    public int maxArea(int[] height) {
        //two pointers -> N 
        //two pointers -> 2*N
        //6,5,4,7,8,2,4,6,9,
        //1 2 3 4 5 6 7 8 9
        //idea: (i ++) (j--) , for two points pointed by two pointers, there must be one big and one small, change the pointer pointed to small so that mamimize the possibility
        int i = 0;
        int j = height.length-1;
        int max  = 0;
        while(i<j){//if i==j break
            //compute the area
            if(height[i]>height[j]){//i bigger
                int temp = (j-i)*(height[j]);
                if(temp>max) max = temp;
                j--;
            }else {
                int temp = (j-i)*(height[i]);
                if(temp>max) max = temp;
                i++;
            }
        }
        return max;
    }
}

 

haishi cai

Leetcode 11. Container With Most Water (two pointers)

原文:https://www.cnblogs.com/stiles/p/leetcode11.html

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