题目描述

• 无
  

代码 & 解题思路

• 思路：使用左右两个指针，不断缩小范围，并在每次缩小的过程对最大值进行更新。
• 代码实现不难，主要是弄明白为啥这样做就能得到正确的值
• 简单描述就是：每次舍弃掉上图中的一根“柱子”，选择左右指针中较矮的柱子。
• 为什么呢？因为对于被舍弃的柱子，它已经完成了它的任务，即“获取该柱子能组合出的最大的容器值”。之后另外一个指针无论如何再向舍弃柱子方向移动，都不可能再取得更大的值了（因为容器实际高度按照小了算），所以可以缩小左右指针容纳的范围。

class Solution {
    public int maxArea(int[] height) {
        /**
            双指针法：
            1. 代码实现不难
            2. 主要是算法正确性验证

         * 把问题缩小
        */

        int len = height.length;
        int left = 0, right = len-1;
        int max = 0;

        while(left != right){
            // 维护 max
            max = Math.max(max, 
            	Math.min(height[left], height[right]) * (right - left));
            // 缩小范围
            if(height[right] < height[left])
                right--;
            else
                left++;
        }
        return max;
    }
}

• 时间复杂度 O(n)，即使遍历一次数组
• 空间复杂度 O(1)