11. Container With Most Water

四刷 06/2022

没有二刷写的那么复杂，还是用了偷懒的哪个短就改哪个的方法

Time O(N)

Space O(1)

Runtime: 5 ms, faster than 50.35% of Java online submissions for Container With Most Water.

Memory Usage: 81.1 MB, less than 39.37% of Java online submissions for Container With Most Water.

class Solution {

    public int maxArea(int[] height) {

        int start = 0, end = height.length - 1;

        int max = 0;

        while (start < end) {

            max = Math.max(max, (end - start) * Math.min(height[start], height[end]));

            if (height[start] < height[end]) {

                start++;

            } else {

                end--;

            }

        }

        return max;

    }

}

二刷
Version #2 Two pointers

77.54 % 
一开始写的跟一刷一样，发现速度很慢
后来想了一下，因为two pointers walking towards each other
So the width of the rectangle is shrinking
only if the height grows, the volume can be larger than the previous max value


public class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length <= 1) return 0;
        int left = 0, right = height.length - 1;
        int minHeight = 0;
        int maxVolumn = 0;
        while (left < right) {
            minHeight = Math.min(height[left], height[right]);
            maxVolumn = Math.max(maxVolumn, (right - left) * minHeight);
            while (left < right && height[left] <= minHeight) left++;
            while (left < right && height[right] <= minHeight) right--;
        }
        return maxVolumn;
    }
}

一刷
Version #1 Two pointers
38.38% 

public class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0) return 0;
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        while (left < right) {
            maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}
三刷
88.16 %

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