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

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

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

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

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

單調棧

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

單調遞增棧：棧內的元素從棧頂到棧低是遞增的。也就是棧頂的最小，棧底最大。

單調遞減棧：棧內的元素從棧頂到棧底是遞減的，也就是棧頂的最大，棧底最小。

構建單調棧模板

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

//構建單調遞增棧

stack = []?? //單調棧

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

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

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

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

????? stack.pop()

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

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

? else:

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

? stack.append(nums[index])

延伸閱讀：

二、棧是什么

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