11.盛最多水的容器

一、题目

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

二、相关链接

• 题目链接：https://leetcode-cn.com/problems/container-with-most-water/
• 参考题解：https://leetcode-cn.com/problems/container-with-most-water/solution/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/

三、解题思路

• 解法：双指针
• 思路： 遍历数组得到所有情况(这里通过双指针可减少遍历)，得到最大值
• 步骤：
  • 1.定义头尾的双指针
  • 2.开始往中间遍历(直到重合)，小的往大的推进

四、代码

public class ContainerWithMosWater {
  /**
   * 左右指针
   * 一个从头一个从尾，哪个比较小就移动(每次移动都判断当前是否最大值)
   *  1.定义头尾的双指针
   *  2.开始往中间遍历(直到重合)，小的往大的推进*
   * @param height
   * @return
   */
  public int maxArea(int[] height) {
    if (height.length <= 1) {
      return 0;
    }

    int max = 0;//结果值(最大值)
    int left = 0;//左指针
    int right = height.length - 1;//右指针

    while (left < right) {
      //判断当前能装多少水
      int cur = 0;
      //以最大值为目标，小的就往大的靠拢
      if (height[left] <= height[right]) {
        cur = (right - left) * height[left];
        left++;
      } else {
        cur = (right - left) * height[right];
        right--;
      }

      max = Math.max(cur, max);
    }

    return max;
  }
}

五、总结

• 难度：简单看题解后可完成
• 备注：一开始不清楚有这种解法，后面看到可以这么解就会了