單調堆疊問題：
要知道單調堆疊的適用于解決什么樣的問題，首先需要知道單調堆疊的作用，單調堆疊分為單調遞增堆疊和單調遞減堆疊，通過使用單調堆疊我們可以訪問到下一個比他大（小）的元素（或者說可以），
也就是說在佇列或陣列中，我們需要通過比較前后元素的大小關系來解決問題時我們通常使用單調堆疊，下面我們通過簡單介紹單調減堆疊和單調增堆疊問題來進一步說明使用單調堆疊處理問題的程序，
什么時候使用單調堆疊？
通常是一維陣列，要尋找任一元素右邊（左邊）第一個比自己大（小）的元素，且要求 O(n) 的時間復雜度
單調堆疊原理：
單調遞增堆疊：從 堆疊底 到 堆疊頂 遞增，堆疊頂大
單調遞減堆疊：從 堆疊底 到 堆疊頂 遞減，堆疊頂小
python模板套路：
1): 當前項向右找第一個比自己大的位置 —— 從右向左維護一個單調遞減堆疊，
def nextGreaterElement_01(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length - 1, -1, -1):
while stack and stack[-1] <= nums[i]:
stack.pop()
if stack:
res[i] = stack[-1]
stack.append(nums[i])
return res
或者 當前項向右找第一個比自己大的位置 —— 從左向右維護一個單調遞減堆疊，
def nextGreaterElement_011(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
res[idx] = nums[i]
stack.append(i)
return res
2)：當前項向右找第一個比自己小的位置 —— 從右向左維護一個單調遞增堆疊
def nextGreaterElement_02(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length - 1, -1, -1):
while stack and stack[-1] >= nums[i]:
stack.pop()
if stack:
res[i] = stack[-1]
stack.append(nums[i])
return res
3): 當前項向左找第一個比自己大的位置 —— 從左向右維護一個單調遞減堆疊
def nextGreaterElement_03(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length):
while stack and stack[-1] <= nums[i]:
stack.pop()
if stack:
res[i] = stack[-1]
stack.append(nums[i])
return res
4): 當前項向左找第一個比自己小的位置 —— 從左向右維護一個單調遞增堆疊
def nextGreaterElement_04(nums: list):
length = len(nums)
res, stack = [-1] * length, []
for i in range(length):
while stack and stack[-1] >= nums[i]:
stack.pop()
if stack:
res[i] = stack[-1]
stack.append(nums[i])
return res
參考來源：https://leetcode-cn.com/problems/next-greater-element-i/solution/dan-diao-zhan-zong-jie-by-wu-xian-sen-2/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/267126.html
標籤：python