本周的题目有点意思,有点“奥数题”的感觉,难度级别也是"Medium"...
题目:现在有n个非负整数a1,a2,…,an，每个数代表一个点(i, ai)，每个点做x轴的垂线<(0,i), (i,ai)>。每两条这样的竖线和x轴一起构成一个容器，找到能装最多水的那个容器。
- 注:n>=2，且不能倾斜容器
说说题目吧,其实就是两条竖线和x轴形成的最大的蓝色矩形面积，如下图：
我的思路一开始比较low,就是冒泡排序的思想,把所有的“矩形”全都算出来，然后再找最大的矩形面积，代码如下：
int maxArea(int* height, int heightSize) {
//water表示蓝色的面积，H是高，W是宽（下同）
int water = 0,H = 0,W = 0;
for (int i = 0;i < heightSize - 1;i++){
for (int j = i + 1;j < heightSize;j++) {
H = height[i] > height[j] ? height[j] : height[i];
W = j - i;
if (H * W > water) water = H * W;
}
}
return water;
}
这个从理论上来说没什么问题，当效率太低，执行的时候超时。。。只能换个思路，从两边到中间(代码更能解释思路)，如下图:
实现代码:
int maxArea(int* height, int heightSize) {
int water = 0,H = 0,W = 0,i = 0,j = heightSize - 1;
while (i < j) {
H = height[i] > height[j] ? height[j] : height[i];
W = j - i;
water = H * W > water ? H * W : water;
//这句注释代码是我特意写在这里的，如果加了这句printf代码，这个算法依旧会超时，这是需要注意的，如果想看输出，建议使用getchar函数
//printf("i=%d,j=%d,H=%d,W=%d,water=%d\n",i,j,H,W,water);
//不断的向右移,找出比H高的竖线停止移动
while (i < j && height[i] <= H) i++;
//不断的向左移,找出比H高的竖线停止移动
while (i < j && height[j] <= H) j--;
}
return water;
}
代码不难，主要是思路,方法也不止一种,条条大路通罗马。。。
