> 文档中心 > 【刷】leetcode字节跳动面试题之盛最多水的容器

【刷】leetcode字节跳动面试题之盛最多水的容器


盛最多水的容器

原题链接

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

解法

我们首先想到的肯定是暴力解法,两个循环,然后比较最大值,这样做时间复杂度就变的较高,这样虽然也可以解出来,但是在面试的时候影响面试官对你的印象,不合适,所以我们要另辟蹊径

这道题最佳的方法是使用指针的解法,还有点博弈论的味道。

至于咋想到用双指针,做题多了自然就会了(当我放屁)

思路

首先我们看这道题知道
两个柱子围成水的面积 = 柱子最小的高度 * 两个柱子的下标相减

我们用两个指针,第一个指针指向数组的第一个位置,第二个指针指向数组的最后一个位置,求出面积
那么如何让指针移动呢?我们让每次最小的那根柱子进行移动就可以了,然后求出在求出面积,最终比较求出最大值

func maxArea(height []int) int {    var max,left,right int = 0,0,len(height) - 1 for left < right { h := 0 l := right - left  if height[left] < height[right] {     h = height[left]     left++   } else {     h = height[right]     right-- } water := l * h if water > max {     max = water }    }    return max}