思路参考前人,复杂度是O(n) java


  • -1

    '''
    import java.util.ArrayList;
    import java.util.List;

    public class Solution {
    public int maxArea(int[] height) {

    	int left = 0;
    	int right = height.length - 1;
    	
    	// 如果只有一个最大值,是可以严格递增的, 但是可能有两个相等的最大值,所以只能是弱递增
    	
    	
    	
    	//从左到右的递增高度的下标,  <= 不是严格<
    	List<Integer> leftList = new ArrayList<Integer>();
    	leftList.add(left);
    	for(int i = 0; i < height.length; i++) {
    	    //这个关系必须有=,没有下面就是错误的,是要设计到相等的两个高度
    			if (height[leftList.get(leftList.size() - 1)] <= height[i]) {
    				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]));
    	if (leftList.size() == 1 && rightList.size() == 1) {
    		return maxArea;
    	}
    	
    	
    	
    	int i = 0;
    	int j = 0;
    	
    	
    	//条件的判断涉及到最大值的分布位置问题, 而且还涉及到最大值有几个
    	//如果最大值只有一个,那么left,right 最后是==关系, 如果有两个 ,那么left 要超过right ,所以最终 left >=right
    	while (left < right) {
    		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.