How to improve this method (Java)


  • 0
    S

    The idea is keep two pointer, one from left, the other from right. For a given left number, find the first one from right that is no less than it. I try to make it O(n) by using two hashmap keep track of each number I come across.

    But there is a problem when left is 2, and right is 200000, I need to put into map 199998 times.

    public class Solution {
        public int maxArea(int[] height) {
            Map<Integer, Integer> rightMost = new HashMap<Integer,Integer>();
            Map<Integer, Integer> leftMost = new HashMap<Integer, Integer>();
            int left = 0, right = height.length-1;
            int max = 0;
            while(left < right){
                while(left < right && leftMost.containsKey(height[left])) left++;
                leftMost.put(height[left],left);
                if(rightMost.containsKey(height[left])) max = Math.max(max,(right-left)*height[left]);
                else{
                    while(left < right && height[right] < height[left]){
                        max = Math.max(max,(right-left)*height[right]);
                        rightMost.put(height[right], right);
                        right--;
                    }
                    for(int i = height[left];i <= height[right];i++)
                        rightMost.put(i,right);
                    max = Math.max(max,(right-left)*height[left]);
                }
            }
            return max;
        }
    }

  • 0
    S

    As your idea "find the first one from right that is no less than it". I write the following code, which cost 382ms

    public class Solution {
    	public int maxArea(int[] height) {
    		int max = 0, i = 0, j = height.length - 1;//i from left, j from right
    		max=Math.min(height[i],height[j])*(j-i);
    		while(i<j){
    			int h=height[j];
    			if(height[i]<height[j]){
    				h=height[i]; //h=1
    				i++;
    				while(i<j && height[i]<=h) i++;							
    			}else{
    				j--;
    				while(i<j && height[j]<=h) j--;
    			}
    			h=Math.min(height[i], height[j]);
    			max=Math.max(h*(j-i), max);
    		}		
    		return max;
    	}
    }
    

    As a comparation, I post my original two pointer code here, which costs 391ms

    public class Solution {
    	public int maxArea(int[] height) {
    		int max = 0, i = 0, j = height.length - 1;
    		while (i < j) {
    			int h = height[j],size;
    			if (height[i] < height[j]) {
    				h = height[i];
    				i++;
    			} else j--;
    			size = h * (j - i + 1);
    			if (size > max) max = size;
    		}
    		return max;
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.