This is the seventh day of my participation in the August More text Challenge. For details, see:August is more challenging

11, Container With Most Water

The question:

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]. the max area of water (blue section) the container can contain is 49.Copy the code

Example 2:

 Input: height = [1,1]
 Output: 1
Copy the code

Example 3:

Height = [4,3,2,1,4] Output: 16Copy the code

Example 4:

 Input: height = [1,2,1]
 Output: 2
Copy the code

Constraints:

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

Problem solving:

1. The cycle of violence

The idea is simple and easy to implement. If more cases are executed on LeetCode, the corresponding code will not be attached here.

* 
 * 
 */
public static int getMaxArea(int[] height) {
    if (Objects.isNull(height)) {
        return 0;
    }
    // Create a variable to store the maximum value, which is computed continuously in double traversal.
    int maxArea = 0;
    int temp = 0;
    for (int i = 0; i < height.length - 1; i++) {
        for (int j = i + 1; j < height.length; j++) {
            temp = (j - i) * Math.min(height[i], height[j]);
            if(temp > maxArea) { maxArea = temp; }}}return maxArea;
}
Copy the code

2, double pointer mode

Similar problem, given a sequence, find the maximum value of the sum of two numbers in the sequence, double pointer also applies

Move the pointer from the two nodes of the sequence, calculate the value of the rainwater from the two nodes, and then gradually move the subscript to the middle. The strategy of moving the subscript: compare the smaller column of the two subscripts with the adjacent nodes

 /** * Double pointer method, one by one * 
 * on the paper to draw the core comparison step diagram * 
 */
 public static int getMaxAreaWithTwoPointer(int[] height) {
     int i = 0;
     int j = height.length - 1;
     int result = 0;
     int temp = 0;
 ​
     while(i ! = j) { temp = (j - i) * Math.min(height[i], height[j]);if (temp > result) {
             result = temp;
         }
         if (height[i] > height[j]) {
             j--;
         } else{ i++; }}return result;
 }
Copy the code