尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 305
已运行时间: 1057
目录
  1. 思路
    1. 暴力循环解决
    2. 两端双指针移动解决

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 305
已运行时间: 1057

思路

暴力循环解决

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

评论区

Twikoo giscus