Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Hold the most water

  1. Min (height[a],height[b])*(b-a)

Method one: enumeration of violence

  1. Double layer for, find all possible areas, pick the maximum
  2. Disadvantages: High time complexity n^2, Leetcode run does not pass
/** * double for loop, one by one, * * @height * @return */ public static int maxArea(int[] height) {int Max = 0; For (int I = 0; for (int I = 0; i < height.length - 1; i++) { for (int j = i + 1; j < height.length; Int area = (height[I], height[j]); int area = (height[I], height[j]); max = Math.max(area, max); } } return max; }Copy the code

Method two: the left and right Pointers converge to the middle

  1. Create left and right Pointers on the left and right sides.
  2. Every time I move the shorter pointer to the middle, why is that? Because as I move to the middle, (b-a) gets shorter, so if I move the shorter pointer, it’s possible to find a larger area.
/** * for loop, with two Pointers converging from both sides of the array, * @param height * @return */ public static int maxArea2(int[] height) {int Max = 0; int left = 0; int right = height.length - 1; Math.min(height[right], height[left]); math.min (height[right], height[left]); // compare area Max = math.max (area, Max); if (height[left] < height[right]) { left++; } else { right--; } } return max; ** @param height * @return */ public static int maxArea3(int[] height) {int Max = 0; int left = 0; int right = height.length - 1; Int area = height[right] > height[left]? Int area = height[right] > height[left]? (right - left) * height[left++] : (right - left) * height[right--]; max = Math.max(area, max); } return max; }Copy the code