11. Container With Most Water

key tips

双指针+贪心法

algorithm 1

从暴力法开始，遍历所有组合(h[i], h[j])。
开始剪枝：

• 首先，由于对称性，(h[i], h[j]) 与(h[j], h[i])等价，因此i从0开始，j从n-1(n=len(h))开始遍历，并且需要保证i < j;

n= len(h)-1;
for (i := 0; i < n; i++){
  for (j = n-1; j > i; j--){
    ...
  }
}

• 其次，由于i增加时伴随着宽度的减少（width = j-i），因此需要在h上补偿，这里选择改变高度小的指针，使得最小height变大，才有可能补偿width的损失

if (h[i] < h[j]) {
  j--;
}else {
  i++;
}