本周的題目有點(diǎn)意思,有點(diǎn)“奧數(shù)題”的感覺,難度級別也是"Medium"...
題目:現(xiàn)在有n個非負(fù)整數(shù)a1,a2,…,an，每個數(shù)代表一個點(diǎn)(i, ai)，每個點(diǎn)做x軸的垂線<(0,i), (i,ai)>。每兩條這樣的豎線和x軸一起構(gòu)成一個容器，找到能裝最多水的那個容器。
- 注:n>=2，且不能傾斜容器
說說題目吧,其實(shí)就是兩條豎線和x軸形成的最大的藍(lán)色矩形面積，如下圖：
我的思路一開始比較low,就是冒泡排序的思想,把所有的“矩形”全都算出來，然后再找最大的矩形面積，代碼如下：
int maxArea(int* height, int heightSize) {
//water表示藍(lán)色的面積，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;
}
這個從理論上來說沒什么問題，當(dāng)效率太低，執(zhí)行的時候超時。。。只能換個思路，從兩邊到中間(代碼更能解釋思路)，如下圖:
實(shí)現(xiàn)代碼:
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函數(shù)
//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;
}
代碼不難，主要是思路,方法也不止一種,條條大路通羅馬。。。
