一、單調(diào)棧什么時候從后向前遍歷，什么時候從前向后遍歷

如果是求右邊的名列前茅個最大，那么就是從右向左遍歷，構(gòu)建單調(diào)遞增棧。

如果是求右邊的名列前茅個最小，那么就是從右向左遍歷，構(gòu)建單調(diào)遞減棧。

如果是求左邊的名列前茅個最大，那么就是從左向右遍歷，構(gòu)建單調(diào)遞增棧。

如果是求左邊的名列前茅個最小，那么就是從左向右遍歷，構(gòu)建單調(diào)遞減棧。

單調(diào)棧

棧是我們都很熟悉的一種數(shù)據(jù)結(jié)構(gòu)，特點就是先進后出。而單調(diào)棧就是這個棧中的元素大小還是單調(diào)的（遞增或者遞減）。單調(diào)棧對于處理 下一個更大/更小元素 有很高的效率。下面我們來介紹下。

單調(diào)遞增棧：棧內(nèi)的元素從棧頂?shù)綏５褪沁f增的。也就是棧頂?shù)淖钚?，棧底最大?/p>

單調(diào)遞減棧：棧內(nèi)的元素從棧頂?shù)綏５资沁f減的，也就是棧頂?shù)淖畲?，棧底最小?/p>

構(gòu)建單調(diào)棧模板

構(gòu)建單調(diào)棧，就是有一個數(shù)字序列nums = [1,3,4,2]，根據(jù)該數(shù)字序列，來構(gòu)建單調(diào)棧。

//構(gòu)建單調(diào)遞增棧

stack = []?? //單調(diào)棧

numMap = {}?? //記錄下一個更大的元素

for index in range(len(nums)-1, -1, -1):

? while(len(stack) != 0 and stack[-1] <= nums[index]):

????? //棧頂元素<=當(dāng)前數(shù)據(jù)時，出棧，直到棧頂元素 大于 當(dāng)前數(shù)據(jù)，當(dāng)前數(shù)據(jù)入棧，才符合單調(diào)遞增。

????? stack.pop()

? if(len(stack) == 0):

????? numMap[nums[index]] = -1

? else:

????? numMap[nums[index]] = stack[-1]

? stack.append(nums[index])

延伸閱讀：

二、棧是什么

棧是一種先進后出、后進先出的數(shù)據(jù)結(jié)構(gòu)，棧和隊列應(yīng)該是最簡單的兩種數(shù)據(jù)結(jié)構(gòu)了，其原理與實現(xiàn)非常簡單。單調(diào)棧中的元素是嚴(yán)格單調(diào)遞增或者遞減的，也就是說：從棧底到棧頂，元素的值逐漸增大或者減小。雖然單調(diào)棧的性質(zhì)很簡單，但是其用處很大，可以用于求解元素的左右大小邊界問題。