【leetcode】 11. Container With Most Water

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

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

解法1

暴力破解法

时间复杂度：O(n^2)

思路：两次遍历数组，取长度较小值与两点下标之差的乘积即面积，记录下面积最大值

int maxArea(vector<int>& height) {
  int var = 0;
  int high = 0;
  int area = 0;
  for (int i = 0; i < height.size(); i ++)
  {
    for (int j = i + 1; j < height.size(); j ++)
    {
      high = height[i] > height[j] ? height[j]:height[i];
      area = high * (j - i);
      if (area > var)
      {
        var = area;
      }
    }
  }

  return var;
}

解法2

双指针

时间复杂度：O(n)

思路：头尾指针，向中间移动，每次都移动长度较小一端（因为宽度逐渐缩小，以该点的长度为基准的面积不可能再大了），计算面积，取面积最大值

int maxArea(vector<int>& height) {
  int left = 0, right = height.size() - 1;
  int var = 0;
  int high = 0;
  int area = 0;
  while(left < right)
  {
    if (height[left] <= height[right])
    {
      high = height[left];
      left ++;
    }
    else
    {
      high = height[right];
      right --;
    }

    area = high * (right - left + 1);
    if (area > var)
    {
      var = area;
    }
  }
  return var;
}