Container With Most Water

• medium
• tag: two pointers
• similar: trapping rain water

对撞型指针里面的经典: 灌水.

思路:

• 最简单的就是枚举每一对板子的组合, 同时update max. 这样是O(N^2)的复杂度.
• 实际上可以通过对撞型指针以及trapping water的性质可以忽略一部分的情况. 从而做到O(N).

对撞指针

• 关键在于怎么利用trapping water的性质.
• 2块板子围城的面积由短的确定.

• 最重要的性质:

  • 在如下代码里面, 为什么可以直接: l++, 或者r--? 以height[l] < height[r]为例, 这里直接l++, 从而忽略了[l,l+1], [l,l+2], ..., [l, r-1]?
  • 很简单, 分情况讨论:
    1. 若height[l+k] < height[l], 则短板更小, 而且宽度更小, 所以面积更更小!
    2. 若height[l+k] > height[l], 则虽然短板不变, 但是宽度小了, 所以面积必然小.

  • 综上所述, 每次都直接忽略短板, 并移动短板, 尝试看看有没有找到其他组合使得面积更大.

  • 如下图所示: . 注意看a,b这2中情况, 分别对应上面的讨论的1,2.

• 代码如下:

  public int maxArea(int[] height) {
    if (height == null || height.length <2) {
      return 0;
    }
    int l = 0, r = height.length-1;
    int ans = Integer.MIN_VALUE;
    while (l <= r) {
      if (height[l] <= height[r]) {
        ans = Math.max(ans, height[l] * (r-l));
        l++;  // 为什么不用考虑: [l,l+1], [l,l+2], ..., [l, r-1]?
      }
      else {
        ans = Math.max(ans, height[r] * (r-l));
        r--;
      }
    }
    return ans;
  }
  

反思

• 虽然是第n次做, 也知道使用对撞指针, 但还是混乱.

  • 我先是记得分2种情况, 但总是想着要判断中间的板子和2边的板子构成的面积有3种情况, 然后就混乱了.
  • 也就是我还是忘了loop的关键是明确loop invariant. 上面是因为我不知道怎么想着计算$$S{i,i'}和S{i',j}$$的面积了, 晕...
  • 这里的invariant应该是i,j所围成的面积!

• 所以应该记住, loop invariant是计算$$S_{i,j}$$, 每次根据i,j的高度来改变i,j.