一、單調棧什么時候從后向前遍歷,什么時候從前向后遍歷
如果是求右邊的名列前茅個最大,那么就是從右向左遍歷,構建單調遞增棧。
如果是求右邊的名列前茅個最小,那么就是從右向左遍歷,構建單調遞減棧。
如果是求左邊的名列前茅個最大,那么就是從左向右遍歷,構建單調遞增棧。
如果是求左邊的名列前茅個最小,那么就是從左向右遍歷,構建單調遞減棧。
單調棧
棧是我們都很熟悉的一種數據結構,特點就是先進后出。而單調棧就是這個棧中的元素大小還是單調的(遞增或者遞減)。單調棧對于處理 下一個更大/更小元素 有很高的效率。下面我們來介紹下。
單調遞增棧:棧內的元素從棧頂到棧低是遞增的。也就是棧頂的最小,棧底最大。
單調遞減棧:棧內的元素從棧頂到棧底是遞減的,也就是棧頂的最大,棧底最小。
構建單調棧模板
構建單調棧,就是有一個數字序列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])
延伸閱讀:
二、棧是什么
棧是一種先進后出、后進先出的數據結構,棧和隊列應該是最簡單的兩種數據結構了,其原理與實現非常簡單。單調棧中的元素是嚴格單調遞增或者遞減的,也就是說:從棧底到棧頂,元素的值逐漸增大或者減小。雖然單調棧的性質很簡單,但是其用處很大,可以用于求解元素的左右大小邊界問題。