Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream

Problem 1.

Given NNN non-negative integers A1, A2… , ana_1, a_2… , a_na1, A2… An, each number represents a point in the coordinates (I, AI)(I, a_i)(I,ai). Draw NNN vertical lines in the coordinates, and the two endpoints of vertical line III are (I, AI)(I, a_i)(I,ai) and (I,0)(I,0)(I,0). Identify two of these lines so that they, together with the XXX axis, can hold the most water in a container.

Note: you cannot tilt the container, and NNN has a value of at least 2.

Example 1 input: height = [0,1,0,2,1,0,1,3,2,1,2,1,1] The height diagram above is represented by the array [0,1,0,2,1,0,1,3,2,1,2,1,1], in which case six units of rain can be caught (the blue parts are rain). The vertical lines in the figure represent the input array [1,8,6,2,5,4,8,3,7]. In this case, the maximum amount of water the container can hold (shown in blue) is 49. Example 2: input: height = [4,2,0,3,2,5] output: 9Copy the code

2.

2.1 Method 1: Violence method

The first and most obvious thing to think of is a brute force search to check the size of every two matches, with the following code:

public static int maxArea(int[] height) {

    int max = 0;
    int current;

    for(int i =0; i<height.length - 1; i++){
        for(int j = i+ 1; j< height.length; j++){ current = (j-i) * Math.min(height[i],height[j]); max = Math.max(max,current); }}return max;
}
Copy the code

Complexity analysis:

  • Time complexity: O(n²).
  • Space complexity: O(1).

2.2 Method 2: Double-pointer method

The area formed between two line segments is always limited by the length of the shorter one. We use two Pointers, one at the beginning and one at the end. In each step, we calculate the area formed by the two lines that the pointer points to and move the pointer that points to the shorter line one step closer to the longer one. As follows:

public static int maxArea2(int[] height) {

    int max = 0;
    int current = 0;
    int left = 0;
    int right = height.length-1;

    while(left < right){
        current = (right - left) * Math.min(height[left],height[right]);
        max = Math.max(max,current);

        if(height[left] < height[right]){
            left ++ ;
        }else{ right -- ; }}return max;
}
Copy the code

Complexity analysis:

  • Time complexity: O(n).
  • Space complexity: O(1).

Microsoft and Google have organized a group of interview questions, you can add administrator VX: sXXZS3998 (note the gold dig), to participate in the discussion and livestream