leetcode11 盛最多水的容器

这个题的解题思路为，使用左右两根指针往中间移动去计算面积，在移动过程中，宽度是逐渐减小的，只有高度高于之前点的高度，才有可能产生更大的面积。

先贴出自己的解法，时间复杂度为O(N),空间复杂度为O(1)

class Solution {

    public int maxArea(int[] height) {

        int maxNum = 0;

        int start = 0;

        int end = height.length - 1;

        while (start < end) {

            if (height[start] >= height[end]) {

                int h = height[end];

                int area = (end - start) * h;

                if (area > maxNum) {

                    maxNum = area;

                }

                while (h >= height[end] && start < end) {

                    end--;

                }                       

            } else {

                int h = height[start];

                int area = (end - start) * h;

                if (area > maxNum) {

                    maxNum = area;

                }

                while (h >= height[start] && start < end) {

                    start++;

                }         

            }

        }

        return maxNum;        

    }

}

再贴官方解法，官方解法更简洁，但是每移一步，都比较了一次是否是最大值，比较浪费，应该先比较高有没有变高，没变高就一直移动。

class Solution {

    public int maxArea(int[] height) {

        int maxarea = 0, l = 0, r = height.length - 1;

        while (l < r) {

            maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));

            if (height[l] < height[r])

                l++;

            else

                r--;

        }

        return maxarea;        

    }

}