題目描述
初步分析
情況1：未遇到全局最大值之前
該情況只需要保存現(xiàn)在的截止目前的臨時(shí)最大值tempMax签餐，然后積水體積是tempMax-height[i]。
情況2：已經(jīng)遍歷過(guò)了全局最大值，后面的數(shù)值雖然有局部極值，但沒(méi)有再出現(xiàn)全局最大值
情況3：已經(jīng)遇到全局最大值，但是遇到了第二個(gè)極值比之前遇到的第一個(gè)極值要大晌梨，那么積水的體積就是全局最大值和第二次的遇到的極值（即次大值）之間的容積了
總結(jié)情況2和情況3，在第三次遇到的極值要和次大值比較须妻。
情況4：其實(shí)這里和情況1是一樣的
為什么這里會(huì)列出來(lái)這個(gè)呢仔蝌？
因?yàn)轭}目要求只能遍歷一次數(shù)組，我們不確定在一次遍歷的過(guò)程中是不是還能碰到全局最大值荒吏，所以敛惊，這里考慮局部極值和全局最大值的關(guān)系就顯得尤為重要。
相比情況2和情況3绰更，在第三次遇到的極值要和最大值比較瞧挤。
我們要在一次遍歷的過(guò)程中判斷局部極值點(diǎn)锡宋，然后比較局部極值點(diǎn)和暫時(shí)的最大值和次大值的大小關(guān)系，根據(jù)不同的情況來(lái)做出相應(yīng)的動(dòng)作特恬。
反其道而行之
上面的分析看似把情況都考慮到了执俩，但這使得問(wèn)題擴(kuò)散開(kāi)來(lái)。尤其是當(dāng)階段性的極值不是最大值也不是次大值的情況就無(wú)法解決癌刽。所以役首，我們應(yīng)該反其道而行之，換個(gè)角度來(lái)簡(jiǎn)化問(wèn)題妒穴。
我們一直在考慮當(dāng)遇到最大值之后宋税，如何進(jìn)行比較來(lái)計(jì)算后續(xù)的蓄水容積的情況摊崭，但這樣不如從最后設(shè)定一個(gè)下標(biāo)來(lái)反向計(jì)算讼油。于是這就形成了解決這個(gè)問(wèn)題的核心思路：分別從頭尾設(shè)置兩個(gè)下標(biāo)i，j呢簸，首先比較這兩個(gè)下標(biāo)對(duì)應(yīng)的值的大小矮台，由對(duì)應(yīng)值小的那個(gè)下標(biāo)先移動(dòng)，并記錄該下標(biāo)的當(dāng)前的臨時(shí)最大值（比如i先移動(dòng)根时，記錄i_max）瘦赫，當(dāng)遇到一個(gè)新的最大值的時(shí)候，不但要對(duì)i進(jìn)行局部變量的清零蛤迎，還要比較該最大值與j所對(duì)應(yīng)值的大小關(guān)系确虱，然后較小值對(duì)應(yīng)的下標(biāo)繼續(xù)移動(dòng)，直到兩個(gè)下標(biāo)相遇替裆，遍歷了一遍數(shù)組為止校辩。
程序代碼
int Volume(int* height, int n)
{
int i = 0;
int j = n-1;
int i_max = height[i];
int j_max = height[j];
int volume = 0;
const int i_walk = 1;
const int j_walk = 2;
//i_max <= j_max , i先走
int who_walk = i_max <= j_max ? i_walk : j_walk;
while(i != j)
{
if(who_walk == i_walk)
{
if(i_max > height[i])
{
volume += i_max-height[i];
}
else
{
i_max = height[i];
if (i_max > j_max)
{
who_walk = j_walk;
continue;
}
}
++i;
}
else if(who_walk == j_walk)
{
if(j_max > height[j])
{
volume += j_max-height[j];
}
else
{
j_max = height[j];
if (j_max >= i_max)
{
who_walk = i_walk;
continue;
}
}
--j;
}
}
return volume;
}
轉(zhuǎn)載請(qǐng)注明作者Jason Ding及其出處
GitCafe博客主頁(yè)(http://jasonding1354.gitcafe.io/)
Github博客主頁(yè)(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡(jiǎn)書主頁(yè)(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
百度搜索jasonding1354進(jìn)入我的博客主頁(yè)
