每天一道Leetcode之盛最多水的容器

tech2022-08-20  67

每天一道Leetcode之盛最多水的容器

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

题目分析

数组问题,n个整数构成的数组。求盛水最多的容器,也就是说根据木桶理论,取决于最短的木板。那么在这个容器中。容器大小可以把三维置换为二维空间。也就是说取决于最短的那条边。那么就是找出数组内每两个数字的中最小的数字*这两个数字的下标值为最小的即可。 最容易想到的就是暴力解法:

func maxArea(height []int) int { var maxArea = 0 for index1, h1 := range height { for index2, h2 := range height { tmpArea := min(h2, h1) * (index2 - index1) maxArea = max(maxArea, tmpArea) } } return maxArea }

那么暴力解法我们的思路是,固定左边,然后让右边一个一个去尝试。我们可不可以,不固定左边。让两边都可以移动。也就是双指针游历。首先最后的结果一定是处于数组中的两个数字。一定在 height[0]到height[max]中,那么如果不考虑高度的影响,一定是height[0]与height[max]组成的矩形最大。要是考虑到高度,就需要两边不断的靠近寻找出最大的值。靠近的方式怎么移动呢。左右两边谁小移动谁。因为谁小就意味着它已经是短板了,移动大的一方一定不会改变结果。因为任何Area1 = min(left, right) * weight。假设 右侧的值小于左侧的值,那么移动后 Area2 = min(left,right2) * weight2。首先weight2 一定是小于weight的。right2大或者小与left,如果比left大则此时的面积比之前的大了,否则比之前的小,如果小则继续移动指针。

func maxArea2(height []int) int { i, j, maxArea, tmpArea := 0, len(height)-1, 0,0 for i < j { weight := j-i if height[i] < height[j] { tmpArea = height[i] * weight i++ } else { tmpArea = height[j] * weight j-- } maxArea = max(tmpArea, maxArea) } return maxArea }

以上代码在LeetCode中提交是正确的。如果有不对的地方,欢迎指正。

最新回复(0)