Problem:
Problem Statement
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 the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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 2:
Input: height = [1, 1]
Output: 1
Example 3:
Input: height = [4,3,2,1,4]
Output: 16
Example 4:
Input: height = [1,2,1]
Output: 2
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
Thinking and Solutions:
Well, I thought since this is a Dynamic Programming problem, we can create a recursion function.
And matrix is a 2 dimension matrix and matrix[i][j] store the maximal area from the i-th index to j-th index.
Then I want to find the maximal area among matrix[i][j-1], matrix[i+1][j] and matrix[i]j.
public class Solution {
public static int maxArea(int[] height) {
// Using Dynamic Programming
// This is the area matrix. The first index is the start index. The second index is the ending index.
int[][] matrix = new int[height.length][height.length];
for (int i = 0; i < height.length; i++) {
for (int j = 0; j < height.length; j++) {
matrix[i][j] = -1;
}
}
return maxAreaSub(height, 0, height.length-1, matrix);
}
public static int maxAreaSub(int[] height, int starting, int ending, int[][] matrix) {
if(matrix[starting][ending] != -1){
return matrix[starting][ending];
}
if (ending - starting == 1) {
return Math.min(height[ending], height[starting]);
}
int left = maxAreaSub(height, starting, ending - 1, matrix);
int right = maxAreaSub(height, starting + 1, ending, matrix);
int current = (ending - starting) * Math.min(height[ending], height[starting]);
int maxV = Math.max(Math.max(left, current), right);
matrix[starting][ending] = maxV;
return maxV;
}
}
But a problem was that if the list is very long, like 1000 elements in the list, the matrix is 4M ($4 \time 1000 \time 1000$) for integer matrices.
So I thought building the dynamic programming from bottom to top could be a better way because it is more reasonable. Also, you don't need to store the maximal area matrix. Instead, storing the maximal area list for a certain length could be a good idea to reduce the storage pressure.
public class Solution2 {
public static int maxArea(int[] height) {
// Using Dynamic Programming
// This is the area matrix. The first index is the start index. The second index is the ending index.
int[] miniArea = new int[height.length];
for (int i = 0; i < height.length; i++) {
miniArea[i] = 0;
}
return maxAreaSub(height, 1, miniArea);
}
public static int maxAreaSub(int[] height, int length, int[] miniArea) {
int[] areas = new int[height.length - length];
for (int i = 0; i < height.length - length; i++) {
int left = miniArea[i];
int right = miniArea[i + 1];
int current = length * Math.min(height[i], height[i + length]);
areas[i] = Math.max(current, Math.max(left, right));
}
if (areas.length == 1) {
return areas[0];
}
return maxAreaSub(height, length + 1, areas);
}
}
The storage problem seems to be solved but actually since the recursion function is still too slow, time limit is still exceeded. So here, I sought for others' solutions. This is much easier solution but it seems to work well.
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while(left < right) {
maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
if(height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}
It uses a global maximal area. With 2 pointers right and left, we can find a local area and judge which is the current maximal area.
Also, it has a basic idea that the maximal area is from the maximal length or from shorter length with two higher heights. So just greedy search the longer 2 heights could reduce the running time.
Conclusion
According to the problem, I realize 2 things:
- Reasonable greedy search could be a good way to reduce the running time.
- Writing a
whileinstead of using a recursion function could be a good way for running dynamic programming.
Top comments (0)