这道题的重点是对双指针过程的分析,典型的双指针类型题目,博主的代码速度为16ms,战胜90%的答题者,思路比较一般,不过还是分享一下。

题目

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

分析

分析过程如下,现在有两个指针从左右两端向中间移动,那么盛水的体积等于左右指针指向的最小高度乘以宽度。

如果\(H(left) < H(right)\),那么盛水的体积取决于左边的指针,那么现在开始移动左边的指针。

在移动过程中,更新最小高度,如果发现之后的高度小于之前的高度,那么直接跳过(因为向中间移动的时候宽度肯定变小了,如果高度再变小,那么容积肯定变小),如果发现高度大于之前的高度,那么判断容积。最后返回最大容积即可。 

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注