Question
Formatted question description: https://leetcode.ca/all/11.html
Given n nonnegative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai).
n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
Find two lines, which together with xaxis forms a container, such that the container contains the most water.
Note: You may not slant the container.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
@tagarray
Algorithm
The following is an example: [4,6,2,6,7,11,2] to explain.
1 . First, suppose we find the vertical line that can take the maximum volume as i, j (assuming i<j), then the maximum volume C = min( ai, aj) * (j i);
2 . Below we look at such a property:
 No line at the right end of j will be higher than it! Suppose there is k ( j<k && ak> aj), then ak> aj, so min(ai,aj, ak) =min(ai,aj), so the volume of the container formed by i, k C’= min(ai,aj) * (ki)> C, which is the most contradictory value with C, so there will be no line higher than it behind the proof j; To
 Similarly, there will be no higher line on the left side of i; To What is this indicating? If we currently get the candidate: set x, y as two lines (x< y), then the two new edges that can be larger than it must be in the interval [x,y] And ax’> =ax, ay’>= ay;
3 . So we move closer from the two ends to the middle, and update the candidate values at the same time; when shrinking the interval, first shrink from the smaller edge of x, y;
The intuitive explanation is: volume is area, which is affected by length and height. When the length decreases, the height must increase to increase the area, so we start to decrease from the longest length, and then look for a higher line to update Alternate
Code
Java

public class Container_With_Most_Water { public static void main(String[] args) { Container_With_Most_Water out = new Container_With_Most_Water(); Solution2 s = out.new Solution2(); System.out.println(s.maxArea(new int[]{2,0,2})); } // time: O(N) // space: O(1) public class Solution { public int maxArea(int[] height) { int[] h = height; if(h == null  h.length == 0) { return 0; } int l = 0; // left int r = h.length  1; // right int max = (r  l) * Math.min(h[l], h[r]); // possibly very first position is max area while(l < r) { if(h[l] < h[r]) { l++; } else { r; } max = Math.max(max, (r  l) * Math.min(h[l], h[r])); } return max; } } // N^2. Time Limit Exceeded public class Solution2 { public int maxArea(int[] h) { // h: height if (h == null  h.length == 0) { return 0; } // possibly sanity check for negative int in array, throw something for debugging // never trust the passed in parameter! int i = 0; int max = Integer.MIN_VALUE; while (i < h.length) { int j = i + 1; while (j < h.length) { max = Math.max(max, (j  i) * Math.min(h[i], h[j])); j++; } i++; } return max; } } }

// OJ: https://leetcode.com/problems/containerwithmostwater/ // Time: O(N^2) // Space: O(1) class Solution { public: int maxArea(vector<int>& A) { int N = A.size(), ans = 0; for (int i = 0; i < N; ++i) { if (!A[i]) continue; for (int j = i + 1 + ans / A[i]; j < N; ++j) { ans = max(ans, min(A[i], A[j]) * (j  i)); } } return ans; } };

class Solution(object): def maxArea(self, height): """ :type height: List[int] :rtype: int """ ans = left = 0 right = len(height)  1 while left < right: ans = max(ans, (right  left) * min(height[left], height[right])) if height[left] <= height[right]: left += 1 else: right = 1 return ans