【算法分析与设计】盛更多的水

题目

示例：

示例 1：

思路

直接思路：暴力破解

利用两层for循环来遍历所有情况，时间复杂度是n;

抱着侥幸心理试试，万一过了呢

代码实现

class Solution {
    public int maxArea(int[] height) {
        int max=0;
        int h;
        int w;
        int s;
        for(int i=0;i<height.length;i++){
            for(int j=i+1;j<height.length;j++){
                 h=Math.min(height[i],height[j]);
                 w=j-i;
                 s=w*h;
                 if(s>max){
                     max=s;
                 }
            }
          
        }
        return max;
    }
}

 不出意料，失败了。。。

思路二

分支，迭代都不行，看了题解才直到双指针。

这个双指针开始是在最左和最右边的，那边矮就那边向中间靠近。

可能有人不理解会不会丢失情况。

这个大可放心，因为最开始宽是最大的，向中间移动就是宽度在缩小，而max只能是高度战胜它，所以不会丢失情况。只是遍历一遍所以时间复杂度是o(n)

class Solution {
    public int maxArea(int[] height) {
        int max=0;
        int h;
        int w;
        int s;
        int left=0;
        int right=height.length-1;
        while(left<right){

                 h=Math.min(height[left],height[right]);
                 w=right-left;
                 s=w*h;
                 if(s>max){
                     max=s;
                 }

                if(height[left]<height[right]){
                    left++;
                }else{
                    right--;
                }
            }
          
        
        return max;
    }
}

通过！！！