11. 盛最多水的容器

1.題目描述

給你 n 個非負整數 a1，a2，…，an，每個數代表坐标中的一個點 (i, ai) 。在坐标内畫 n 條垂直線，垂直線 i 的兩個端點分别為 (i, ai) 和 (i, 0) 。找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水。

說明：你不能傾斜容器。

示例 1：

輸入：[1,8,6,2,5,4,8,3,7]

輸出：49

解釋：圖中垂直線代表輸入數組 [1,8,6,2,5,4,8,3,7]。在此情況下，容器能夠容納水（表示為藍色部分）的最大值為 49。

示例 2：

輸入：height = [1,1]

輸出：1

示例 3：

輸入：height = [4,3,2,1,4]

輸出：16

示例 4：

輸入：height = [1,2,1]

輸出：2

提示：

n == height.length

2 <= n <= 105

0 <= height[i] <= 104

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/container-with-most-water

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2.題解

利用雙指針可以解決，代碼很簡單，但是思路很重要。

class Solution {
    public int maxArea(int[] height) {
        int area = 0;
        int left = 0;
        int right = height.length-1;
        while (left<right) {
            area = Math.max(area,(right-left)*Math.min(height[left],height[right]));
            //每次移動指針時，總是移動值相對較小的那個指針，才能保證下一次計算的面積盡可能的大，因為減少的步伐是固定的
            if(height[left]<height[right]){
                left++;
            }else {
                right--;
            }
        }

        return area;
    }
}