时间复杂度 O(n), java


  • 0

    这个题目涉及到有限个数最大值的分布问题, 最大值可能有一个,但是也可能有多个,
    要使用严格递增的从两头向中间来的高度序列, 最后肯定都是落到最大值上,这个是充要条件,
    用下标也行,但是就不是严格递增的序列高度,而必须改成弱递增的高度序列,因为可能有两个最大值

    从左到右,和从右到左的高度序列列表就可能包含重复的不必要的元素了

    '''

     import java.util.ArrayList;
     import java.util.List;
    
     public class Solution {
      public int maxArea(int[] height) {
        
    	
    	int left = 0;
    	int right = height.length - 1;
    	// 找出最大的高度
    	int maxHeight = 0;
    	for (int i = 0; i < height.length; i++) {
    		if (maxHeight < height[i]) {
    			maxHeight = height[i];
    		}
    	}
    	
    	//从左到右严格递增的高度序列, 下标列表
    	List<Integer> leftList = new ArrayList<Integer>();
    	leftList.add(left);
    	for(int i = 0; i < height.length; i++) {
    			if (height[i] > height[leftList.get(leftList.size() - 1)]) {
    				leftList.add(i);
    			}
    		
    	}
    	
    	//从右到左严格递增的高度序列, 下标列表
    	List<Integer> rightList = new ArrayList<Integer>();
    	rightList.add(right);
    	for (int i = right; i >= 0; i--) { 
    		if (height[i] > height[rightList.get(rightList.size() - 1)]) {
    			rightList.add(i);
    		}
    	}
    	
    	
    	// 初始面积
    	int maxArea = (right - left) * (Math.min(height[right], height[left]));
    	
    	
    	
    	
    	int i = 0;
    	int j = 0;
    	// 当左右都达到最大高度时候,停止, 最大高度可能不止一个,
    	while (!(height[left] == maxHeight && height[right] == maxHeight)) {
    		if (height[left] <= height[right]) {
    			i++;
    			left = leftList.get(i);
    		} else {
    			j++;
    			right = rightList.get(j);
    		}
    		
    		int tempArea = (right - left) * (Math.min(height[right], height[left]));
    		if (maxArea < tempArea) {
    			maxArea = tempArea;
    		}
    	}
    	
    	return maxArea;
    	
    	
    }
    

    }

    '''


Log in to reply
 

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