尼采般地抒情

尼采般地抒情

尼采般地抒情

音乐盒

站点信息

文章总数目: 311
已运行时间: 1518

思路

暴力循环解决

  • 对数组各个元素进行第一遍遍历,在此之中以该元素为基准该元素后面的所有元素进行遍历,进行两者最短高度 * (后面元素下标 - 该元素下标)运算,遍历完成即可得到上述值的最大值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
}

评论区