💠 topic

LeetCode title address: leetcode-cn.com/problems/co… Difficulty: Medium Tags: Array, Greedy, double pointer

11. Container that holds the most water

Give you n non-negative integers A1, A2… , a ‘ ‘n, each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.

Note: You cannot tilt the container.

Example 1:

Example 2:

Input: height = [1,1Copy the code

Example 3:

Input: height = [4,3,2,1,4Copy the code

Example 4:

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

Tip:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

📙 answer

💥 Method 1: Violence enumeration method

💡

Violence enumerates all cases

👟 complexity

  • ⏰ Time complexity: O(n2)O(n^2)O(n2)
  • 🌍 Space complexity: O(1)O(1)O(1)

💻 code implementation

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

💥 Method 2: Dual Pointers

💡

Pattern recognition: generally moving the left and right sides of the problem can consider the double pointer.

It can be seen from the question that the capacity is limited by the length of the shorter side. By moving the shorter side to constantly shrink the search scope, find the two sides with the largest capacity of the subscript.

👟 complexity

  • ⏰ Time complexity: O(n)O(n)O(n)
  • 🌍 Space complexity: O(1)O(1)O(1)

💻 code implementation

public int maxArea(int[] height) {
    if (height.length == 0) return 0;
    
    int maxArea = Integer.MIN_VALUE;
    int indexL = 0, indexR = height.length - 1;
    
    while (indexL < indexR) {
        int area = Math.min(height[indexL], height[indexR]) * (indexR - indexL);
        if (area > maxArea) maxArea = area;
        
        if (height[indexL] <= height[indexR]) indexL ++;
        else indexR --;
    }
    return maxArea;
}
Copy the code

🤔 Method Summary

👍 binary find locate short array “splitter” (Java)

Leetcode-cn.com/problems/me…