categories: leetcode

11. Container With Most Water - 图1

题目描述

Given n non-negative integers a, a, …, a, where each represents a point at coordinate (i, a). n vertical lines are drawn such that the two endpoints of line i is at (i, a) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.

11. Container With Most Water - 图2
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example: Input: [1,8,6,2,5,4,8,3,7] Output: 49

参考代码

  1. class Solution {
  2.     public int maxArea(int[] height) {
  3.         int max = 0;
  4.         boolean temp;
  5.         for(int i = 0,j = height.length - 1;i < j;) {
  6.             int h = (height[i] > height[j]) ? height[j] : height[i];
  7.             if(h * (j - i)>max) max = h * (j - i);
  8.             temp = (height[i] < height[j]) ? true : false;
  10.             if(temp) i++;
  11.             else j--;
  12.         }
  13.         return max;
  14.     }
  15. }

思路及总结

较为简单的思路就是采用双指针，从两边往中间逼近，并没有什么边界问题，主要是注意在寻找最多水的容器过程中要一直把较深的一边留下，即沿着较小的边界进行移动（因为较小的边界不可能再产生更多的水）。

参考

https://blog.csdn.net/qq_40435621/article/details/84790436