11. 盛最多水的容器🔖数组🔖双指针

• https://leetcode-cn.com/problems/container-with-most-water/

思路

暴力循环解决

• 对数组各个元素进行第一遍遍历，在此之中以该元素为基准对该元素后面的所有元素进行遍历，进行两者最短高度 * （后面元素下标 - 该元素下标）运算，遍历完成即可得到上述值的最大值result。
• 该元素后面的所有元素进行遍历：这个循环是指定开始索引的位置往后进行的遍历，使用传统for循环或是for in循环

这种解法会超时，写的时候我就感觉到了数组的双循环八成是超时，即便我是第二个循环不找全部元素，但还是超时n^2逃不掉

function maxArea(height: number[]): number {
  let result: number = 0
  height.forEach((data: number, index: number) => {
    if (index !== height.length - 1) {
      for (let i: number = index + 1; i < height.length; i++) {
        let result_temp = Math.min(height[i], data) * (i - index)
        result > result_temp ? (result = result) : (result = result_temp)
      }
    }
  })
  return result

两端双指针移动解决

• 探究解决办法的规律来解决问题，利用双指针在首末端往中间靠，每次移动arr[指针]小的，然后在此次与result相比较。
• 这样只需要遍历一遍即可，时间复杂度为n

function maxArea(height: number[]): number {
  let head: number = 0
  let back: number = height.length - 1
  const result_fun = (head: number, back: number): number => {
    return Math.min(height[head], height[back]) * (back - head)
  }
  let result = result_fun(head, back)

  while (head !== back) {
    height[head] < height[back] ? head++ : back–
    if(result <= result_fun(head, back) ) result = result_fun(head, back)
  }
  return result
}