一、單調棧什么時候從后向前遍歷，什么時候從前向后遍歷

如果是求右邊的名列前茅個最大，那么就是從右向左遍歷，構建單調遞增棧。

如果是求右邊的名列前茅個最小，那么就是從右向左遍歷，構建單調遞減棧。

如果是求左邊的名列前茅個最大，那么就是從左向右遍歷，構建單調遞增棧。

如果是求左邊的名列前茅個最小，那么就是從左向右遍歷，構建單調遞減棧。

單調棧

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

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

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

構建單調棧模板

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

//構建單調遞增棧

stack = []?? //單調棧

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

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

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

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

????? stack.pop()

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

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

? else:

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

? stack.append(nums[index])

延伸閱讀：

二、棧是什么

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