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

双指针法

image.png

  • 两个指针相比,谁小,谁就是瓶颈,就结算谁。
  • 这道题不是求每个杆子的最优解,而是求全局的最优解,

image.png

  • 比如这种情况,根据谁小结算谁的逻辑,现在是结算L这个杆子的水量了,

就是图中蓝色部分,但很明显最优水量应该是L到图中红色杆子的部分,
但这不影响结果,因为这是之前已经结算过的了,已经记录在全局最大里了,
所以每个杆子的最优解不重要,根据谁小结算谁这个逻辑就是对的,
我们是要发现是否还有杆子能使全局水量更大

  1. public int maxArea(int[] height) {
  2. int max = 0;
  3. int l = 0;
  4. int r = height.length - 1;
  5. while (l < r) {
  6. max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
  7. if (height[l] > height[r]) {
  8. r--;
  9. } else {
  10. l++;
  11. }
  12. }
  13. return max;
  14. }