Description
给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器,且 n 的值至少为 2。
示例:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
Analyze
给定的函数如下:
- @param height 一个整数数组
- @param heightSize 数组长度
- @return 符合题意的最大容量
这题是一个比较典型的双指针的题目利用一头一尾两个指针的移动来慢慢缩小范围,把在这过程中的最大值保存起来,注意这里的 “指针” 只是一个概念,并不一定是真正的C语言中的指针,例如在这题,只要用两个整型变量分别等于数组的最大下标和最小下标就行了。
既然是利用双指针解题,首先就要思考几个问题:
- 什么时候退出循环
- 该怎么样缩小指针的范围,即怎样判断指针的下一个指向
第一个问题很简单,因为是从两边向中间移动的,所以只要判断出更小的指针移动到比更大的指针还大的位置就说明数组已经被遍历,可以退出了,当然对这题而言,题中说至少要有两个数,因此循环条件就应该是 pre < last 了,其中 pre 指的是小指针,last 指的是大指针。
要判断怎么缩小指针的范围,得从题目入手。题中说要求到数组中能容纳水的最大值,即求水的面积 s = (last - pre) * min(arr[pre],arr[last]) 的最大值,水的高度取决于两端更小的那个数,而指针一开始指向数组两端,然后向内移动,即面积的底 last - pre 在逐渐变小,因此,面积就由两端的更小的高度决定,要把这个“更小的高度” 尽量变大一点,这样说可能会有点绕,举个例子,就比如给的案例如下:
一开始两指针指向两端,此时底为最大值 8 ,高呢,pre 指向的高是 1,last 指向的高是 7 ,取得高应该是容器的最短木板,所以此时的面积是 1 * 8 ,然后考虑的是该移动哪个指针? 很显然,既然面积取决于短的木板,所以要把短的木板变长,即要把更小的那一段高给去掉,这就是这题的指针移动:把两端的指向更小数的指针向内移动。
搞明白了这一点那么这题实现起来就不难了,通过上面分析知道,这几个过程有好多的比大小的步骤,因此写两个 max 和 min 函数或者是宏定义来方便写程序(C语言好歹也算一门高级语言吧连这个都不做一个内置函数吗)。
最后每次比较面积,把较大的保存下来就行了。
Realization
- 宏定义比较函数
注意这些括号不要落下了,宏定义函数还是多写几个函数会避免很多错误
-
双指针和结果的定义和初始化
-
主循环
-
返回
-
提交
Dictionary
很多人可能会纠结,如果两端的高度一样那该怎么移动呢? 其实只要仔细想想就能明白,当 pre 和 last 指向的高度一样时,假设此时我们移动的是 pre ,那么不论 pre 的下一个比 pre 大还是小,面积都不可能变大,因为底变小了,但是高不可能变大(如果 pre 指向的变大了,那高应该是更小的 last 那边;如果变小了那就更小了),所以移动哪边都没有关系,面积并不是靠其中一边来决定的。
附源代码
#define min(a, b) ((a)<(b)?(a):(b))
#define max(a, b) ((a)>(b)?(a):(b))
int maxArea(int* height, int heightSize){
int pre = 0, last = heightSize-1;
int result = 0;
while(pre < last)
{
result = max((last-pre)*min(height[pre], height[last]), result);
if(height[pre] < height[last])
{
pre++;
}
else
{
last--;
}
}
return result;
}