A - 單調(diào)棧

題目大意

給出項(xiàng)數(shù)為 n 的整數(shù)數(shù)列 1…a1…n。

定義函數(shù) f(i) 代表數(shù)列中第 i* 個(gè)元素之后第一個(gè)大于 a i 的元素的下標(biāo)，即 f(i)=\min_{i a_i} {j}。若不存在，則。若不存在，則f(i)=0。

試求出 f(1…n)。

解題思路

剛開始寫的時(shí)候一知半解，直到昨晚B題才理解單調(diào)棧。

其實(shí)單調(diào)棧就是一種查詢方式，用空間換時(shí)間來降低時(shí)間復(fù)雜度。

舉個(gè)例子，我們要找的是當(dāng)前數(shù)后面第一個(gè)大于他的數(shù)，如果不出意外，遍歷到的數(shù)符合條件，就執(zhí)行操作并清空棧，并把遍歷到的數(shù)入棧，然后遍歷下一個(gè)書。如果遍歷到的這個(gè)數(shù)不符合條件呢？我們讓他入棧來代命，再繼續(xù)看下一個(gè)數(shù)符不符合，如果終于找到了一個(gè)符合條件的數(shù)，那么其實(shí)這個(gè)數(shù)對(duì)于前面一系列入棧的數(shù)都是符合條件的。例如4，3，2，1，4，前四個(gè)數(shù)遞減，全部入棧了，直到第五個(gè)數(shù)終于遞增了，3，2，1都是比4小的，所以3，2，1要對(duì)應(yīng)的數(shù)都是這個(gè)4。而第一個(gè)4繼續(xù)留在棧里，等待后續(xù)查找。

所以的話，對(duì)于這題，可以這么寫單調(diào)棧：遍歷數(shù)列，?？盏脑捑桶阉南聵?biāo)入棧，遇到的數(shù)比棧頂數(shù)小就把這個(gè)數(shù)的下標(biāo)入棧，遇到的數(shù)比棧頂數(shù)大就把這個(gè)數(shù)的下標(biāo)存在臨時(shí)數(shù)組里，棧頂數(shù)出棧，然后再次比較棧頂數(shù)和當(dāng)前數(shù)，直到棧頂數(shù)大于當(dāng)前數(shù)。全部執(zhí)行完后如果棧里還有數(shù)，說明他是最后一個(gè)數(shù)，后面沒有比它大的數(shù)了，在臨時(shí)數(shù)組里標(biāo)記為0。最后按照順序依次輸出臨時(shí)數(shù)組里的數(shù)（下標(biāo)）就好了。

B - 發(fā)射站

題目大意

某地有 N 個(gè)能量發(fā)射站排成一行，每個(gè)發(fā)射站 i 都有不相同的高度 H i，并能向兩邊（兩端的發(fā)射站只能向一邊）同時(shí)發(fā)射能量值為 V i 的能量，發(fā)出的能量只被兩邊最近的且比它高的發(fā)射站接收。顯然，每個(gè)發(fā)射站發(fā)來的能量有可能被 0 或 1 或 2個(gè)其他發(fā)射站所接受。

請(qǐng)計(jì)算出接收最多能量的發(fā)射站接收的能量是多少。

解題思路

這里單調(diào)棧用來儲(chǔ)存下標(biāo)，即元素的位置。

想了挺久才懂，其實(shí)單調(diào)棧就是找離元素最近的大于他或小于他的元素的位置，實(shí)現(xiàn)過程就是把元素每次跟棧頂元素作比較，符合條件就執(zhí)行一次操作，并且彈出棧頂元素，不符合條件就把這個(gè)數(shù)入棧待命，等到下一次出現(xiàn)符合條件的元素，那么前面待命的元素就均與當(dāng)前這個(gè)元素匹配。

舉個(gè)例子就很好理解：?jiǎn)握{(diào)遞增棧，假設(shè)有這么一串?dāng)?shù)：1,4,3,2,5。4大于1，就執(zhí)行一次操作，然后把1從棧里踢掉，4入棧，這樣4就成了下一輪被比較的元素。3比4小，不符合，那就入棧待命，2也比3小，再入棧待命。然后發(fā)現(xiàn)5大于2，終于符合了，而實(shí)際上5對(duì)于4,3,2都是符合的，而由于我入棧的時(shí)候是遞減的，所以用5把棧頂?shù)脑匾粋€(gè)一個(gè)踢掉就好了，然后又讓5入棧。。。上一次操作中已經(jīng)把1給踢掉了，所以不用擔(dān)心會(huì)出現(xiàn)5和前面1比較的情況。

了解完這些之后再來看這道題就比較好懂了。

開三個(gè)數(shù)組分別存高度，發(fā)射的能量，積累的能量，下標(biāo)表示他們的位置，然后遍歷數(shù)組。

向右發(fā)射就和上面的操作一樣，符合就累積一下能量，然后去掉棧頂元素（他發(fā)射完了），不符合就入棧。也可以看成，自己左邊那些比自己矮的元素的能量都被自己吸走了，比如4,3,2,1,5,這個(gè)例子，4321的能量都要累加到5的位置上。

向左發(fā)射的話可以這么考慮，由于單調(diào)棧的特性，這里入棧的元素都是遞減的，所以當(dāng)不符合的時(shí)候，當(dāng)前元素的能量就發(fā)射給棧頂元素。這里每次一次循環(huán)只發(fā)射一次，和之前向右發(fā)射的吸收多個(gè)能量有所區(qū)別。舉個(gè)例子，有4,3,2,1,5幾個(gè)數(shù)，遍歷到3時(shí)，4是棧頂元素，所以3能量發(fā)射給4,3入棧，遍歷到2,2能量給3，2入棧，遍歷到1,1能量給2,1入棧，5大于1，開始向右發(fā)射，直到5把前面四個(gè)元素的能量都吸收（此時(shí)棧內(nèi)元素都彈出了，5入棧）。

最后查找累積能量的數(shù)組的最大值就可。

C - Po

題目大意

有一個(gè)長(zhǎng)度為 n 的數(shù)組。在初始狀態(tài)下，所有元素都為 00。

每次操作，可以將一個(gè)連續(xù)的區(qū)間 [l,r] 內(nèi)的所有數(shù)加上一個(gè)正整數(shù) x，但要求任意兩個(gè)操作區(qū)間要么互不相交，要么一個(gè)包含另外一個(gè)。

請(qǐng)問能將原數(shù)組變?yōu)榻o定數(shù)組 a 的最少操作次數(shù)。

解題思路

以123213為例，如果用圖形來表示，那么就可以把這個(gè)想象成一個(gè)有起伏的山坡，之后，要想清楚一件事，這道題才有思路：這里的區(qū)間相加其實(shí)是可以進(jìn)行變換的，操作[1,3],[2,5]和[1,5],[2,3]得到的結(jié)果其實(shí)是一樣的。那么對(duì)于一個(gè)上坡一個(gè)下坡，兩邊等高的部分其實(shí)只用操作一次，這個(gè)用單調(diào)棧就可以實(shí)現(xiàn)。

遍歷數(shù)組其實(shí)可以看做一個(gè)上下坡的過程，上坡的時(shí)候，遇到高的就入棧并計(jì)數(shù)，到山頂后，遇到矮的，就不斷讓棧頂數(shù)出棧，直到當(dāng)前數(shù)不比棧頂數(shù)小為止，然后比較棧頂數(shù)和當(dāng)前數(shù)，如果相等就continue跳過看下一個(gè)數(shù)就好了，因?yàn)榍懊嫔掀碌臅r(shí)候在登高的位置已經(jīng)計(jì)數(shù)過了。continue的過程可以看做是把當(dāng)前數(shù)水平線以上的山削平，然后比較兩頭的數(shù)。