LeetCode-11.盛最多水的容器

怼烎@ 2022-01-31 05:21 165阅读 0赞

# 题目 #

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

> 说明：你不能倾斜容器，且 n 的值至少为 2。

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]  
解题思路—**双指针**：两条线与x轴形成的长方形面积，长即为两条线在x轴间的距离，宽即为两条线中最短的那条。想要形成的面积最大，**两条线间的距离越长越好，最短的那条线越高越好。所以，可以设置双指针，分别从头尾开始向内遍历**。如何确定是移动指针left还是right呢？需要比较一下left和right的长度，**移动较短的那一根**。这**虽然会缩小矩形的长，但是有可能会增加矩形的宽**。（如果移动较长的那一根，长宽都会减小。）

## Java解题—双指针 ##

class Solution {
        public int maxArea(int[] height) {
            int left = 0, right = height.length-1;
            int max = 0;
            while(left<right){
                int area = 0;
                if(height[left]>height[right]){
                    area = (right-left)*height[right];
                    right--;
                }else{
                    area = (right-left)*height[left];
                    left++;
                }
                max = max<area?area:max;
            }
            return max;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb3l1ZWFjZQ_size_16_color_FFFFFF_t_70]: /images/20220131/ff8f36f24ecf4c81b963ae20d29e345f.png