Problem:
Given n non-negative 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 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.
Examples:
input: [1 3 2 4]
output: 6
explanation: use 3, 4, we have the following, which contains (4th-2nd) * min(3, 4) = 2 * 3 = 6 unit of water.
|
1 2 3 4 |
| |~~| |~~| |~~| |
Idea:
Two pointers
Time complexity: O(n)
Space complexity: O(1)
Solution:
C++ two pointers
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Runtime: 19 ms class Solution { public: int maxArea(const vector<int>& height) { int ans = 0; int l = 0; int r = height.size() - 1; while (l < r) { int h = min(height[l], height[r]); ans = max(ans, h * (r - l)); if (height[l] < height[r]) ++l; else --r; } return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Runtime: 13 ms class Solution { public int maxArea(int[] height) { int l = 0; int r = height.length - 1; int ans = 0; while (l < r) { int h = Math.min(height[l], height[r]); ans = Math.max(ans, h * (r - l)); if (height[l] < height[r]) ++l; else --r; } return ans; } } |