危險的動物解題報告

1、的動物解題【問題描述】給定數(shù)列a1, a2, , an，給出Q 個問題，其中第i 個問題具有如下形式：(Si,Ei)（其中Sii,ajai（規(guī)定 an+1=+）。請在 O(n)的時間復(fù)雜度內(nèi)求出 f1.n。通俗的說，fi就是近最大值”問題)ai 后面第一個比 ai 大的數(shù)的。(故而作者稱之為“最假設(shè)fk+1.n已經(jīng)求出來了，下面考慮求fk。ak+1,ak+2, an 這些數(shù)，如果存在i,j(k+1=ij=aj，那么 aj 就顯然沒有意義了。把 無 意 義 的 數(shù) 都 去 掉 ， 設(shè) 剩 下 的 數(shù) 的ai1ai2ai3ait。如果aki2it ，則 否則 ak=ait，因為 k=ait dot

2、t-1; fk=at;tt+1; at=k; end;i數(shù)組實際上就是一個棧。每個元素至多進棧一次、出棧一次，所以算法時間復(fù)雜度是 O(n)。以上算法有一個缺點：需要用一個 O(n)的棧作為輔助空間。其實不難發(fā)現(xiàn) fit=it-1, fit-1=fit-2,，fi2=i1。因此可以對算法進行如下改造：fn+1+;for in downto 1 do beginfi=i+1;while afi=ai do fiffi;end;這樣就在 O(1)的空間、O(n)的時間復(fù)雜度下，完美的解決了“最近最大值”問題?！緦υ瓎栴}的分析】把所有的區(qū)間按照S 值排序（用基數(shù)排序，空間復(fù)雜度為 O(n)，時間復(fù)雜

3、度為O(n+q)）。不妨設(shè) S1=S2=S3=Sq。因為不存在區(qū)間包含關(guān)系，必然有E1=E2=Eq。首先求(S1,E1)的最大值：max1S1while fmax1=E1 do max1fmax1;算法的原理很簡單。首先假設(shè) max1=S1 是最大值，然后考慮 max1 之后第一個比它大的數(shù)。如果這個數(shù)還在區(qū)間內(nèi)，就更新 max1fmax1；否則說明 max1肯定是S1,T1里面的最大數(shù)了。然后考慮求S2, T2的最大值。一個自然的想法是模仿上面的算法： max2S2while fmax2=E2 do max2fmax2;如果max1=S2 呢？這時候就有冗余運算。因為max1 是S1.T1的

4、最大值，所以肯定也是S2.T1的最大值。因此S2.Max1這一段就沒有必要重新求一次了，可以改進如下：max2maxS2,max1 while fmax2T2 怎么辦？事實上這是絕對不可能的！否則 T2max1=T1T2=S1。綜合起來就是S1=S2=T2T1存在包含關(guān)系！這和題目條件是的！所以 max1肯定不大于T2。這也是為什么能夠直接寫max2maxS2,max1的原因。（“不包含”這個條件是很關(guān)鍵的，如果去掉這個條件，就只能采用標(biāo)準(zhǔn)的RMQ 算法來做，那么編程復(fù)雜度就要大得多；而且效率也大打折扣。）對于之后的區(qū)間S3.T3, S4.T4, ,Sq,Tq都可以類似的操作，形式化的代碼如下

5、：max00;for i1 to Q do beginaxSi,maxi-1 while fmaxi=Ei domaxifmaxiend;下面分析一下復(fù)雜度。把max1, max2, , maxq 看作連續(xù)移動的指針，根據(jù)算法，指針必然是不回溯的，所以求max數(shù)組的時間復(fù)雜度是 O(n)。綜合排序、“最近最大值”問題、輸入輸出，總的復(fù)雜度是：O(n+q)。值得說明的是，它的系數(shù)和 RMQ 算法比較，是相當(dāng)小的。實際運行速度也很快。至此問題就完全解決了?！拘〗Y(jié)】這個問題是很具有“性”的因為它“長得很像”標(biāo)準(zhǔn) RMQ 問題。如果選手一不就可能走上 RMQ 的不歸路。雖然 RMQ 算法能夠很好的解決此題，但是需要花費難以估計的時間和精力來編寫一個復(fù)雜的程序事實上，作者的程序僅僅 70 行，在 20 分鐘之內(nèi)即可完成。關(guān)鍵的變化在于“區(qū)間不包含”。讀者可以自己試一試：一旦出現(xiàn)了區(qū)間包含，問題就變得不那么簡單，本文介紹的方法也就