Given an array of non-negative integers, each of them representing the height of a board perpendicular to the horizontal line, the distance between any two adjacent boards is 1. Consider selecting two boards such that together with the horizontal line they form a container. Find the volume of the largest such container.

Assumptions

• The given array is not null and has size of at least 2

Examples

• { 2, 1, 3, 1, 2, 1 }, the largest container is formed by the two boards of height 2, the volume of the container is 2 * 4 = 8.

Solution: 两指针往内扫，ans = Math.max(ans, Math.min(array[i], array[j]) * (j - i)); 谁小移谁

  public int largest(int[] array) {
    int i = 0, j = array.length - 1, ans = 0;
    while (i < j) {
      ans = Math.max(ans, Math.min(array[i], array[j]) * (j - i));
      if (array[i] <= array[j]) {
        i++;
      } else {
        j--;
      }
    }
    return ans;
  }