單調(diào)棧，棧還能單調(diào)一下？
之前遇到一個(gè)算法題目，自己只會(huì)用時(shí)間復(fù)雜度 O(N^2) 暴力解法解決，有大佬說(shuō)用單調(diào)棧，可以做到 O(N) 的時(shí)間復(fù)雜度，當(dāng)時(shí)我的表情是這樣的：
啥是單調(diào)棧？怎么用呢？我就深入學(xué)習(xí)了一番，于是就有了下文。
什么是單調(diào)棧
單調(diào)棧，首先是一個(gè)棧，滿足先進(jìn)后出的特性，其次是出棧有點(diǎn)特殊：
遇到一個(gè)新元素，如果它比棧頂元素小，那就讓它入棧，否則就彈出棧頂元素，直到這個(gè)新元素比棧頂元素小，再讓它入棧。這樣的話，最終的結(jié)果就是棧內(nèi)的元素是從棧底到棧頂是遞減的，其出棧的順序就是遞增的，這樣的棧叫做單調(diào)遞增棧。
反過(guò)來(lái)就是單調(diào)遞減棧。
聽(tīng)起來(lái)很容易理解，真正實(shí)戰(zhàn)的時(shí)候，還是有點(diǎn)燒腦。
單調(diào)棧的套路
比如說(shuō)這樣一道題目：
給一個(gè)數(shù)組，返回一個(gè)大小相同的數(shù)組。返回的數(shù)組的第 i 個(gè)位置的值應(yīng)當(dāng)是，對(duì)于原數(shù)組中的第 i 個(gè)元素，至少往右走多少步，才能遇到一個(gè)比自己大的元素，如果之后沒(méi)有比自己大的元素，或者已經(jīng)是最后一個(gè)元素，則在返回?cái)?shù)組的對(duì)應(yīng)位置放上 -1。
例如：
輸入 [5,3,1,2,4]
輸出 [-1 3 1 1 -1]
解釋?zhuān)簩?duì)于數(shù)字 5，之后沒(méi)有比它更大的數(shù)字，因此是 -1，對(duì)于數(shù)字 3，需要走 3 步才能達(dá)到 4，對(duì)于 1 和 2，都只需要走 1 步，就可以遇到比自己大的元素。對(duì)于最后一個(gè)數(shù)字 4，因?yàn)橹鬀](méi)有更多的元素，所以是 -1。
你可以把這個(gè)當(dāng)作面試題。
一看這個(gè)題目，我相信你第一眼肯定會(huì)想到暴力解法：針對(duì)每一個(gè)要計(jì)算的數(shù) a，往后遍歷，并計(jì)數(shù) cnt，找到第一個(gè)比 a 大的就將 cnt 填進(jìn)去，找不到就填 -1。時(shí)間復(fù)雜度 O(N^2)。
你能否用時(shí)間復(fù)雜度 O(N) 的方法解呢？
這就需要使用單調(diào)棧了。通過(guò)單調(diào)遞增棧的定義，每當(dāng)遇到元素大于棧頂元素時(shí)，我們就遇到了一個(gè)"大數(shù)"。這個(gè)"大數(shù)"比它之前多少個(gè)數(shù)大我們不知道，但是至少比當(dāng)前棧頂所對(duì)應(yīng)的數(shù)大。我們彈出棧內(nèi)所有對(duì)應(yīng)數(shù)比這個(gè)數(shù)小的棧內(nèi)元素，并更新它們?cè)诜祷財(cái)?shù)組中對(duì)應(yīng)位置的值。因?yàn)檫@個(gè)棧本身的單調(diào)性，當(dāng)棧頂元素所對(duì)應(yīng)的數(shù)比這個(gè)元素大的時(shí)候，我們可以保證，棧內(nèi)所有元素都比這個(gè)元素大。對(duì)于每一個(gè)元素，當(dāng)它出棧的時(shí)候，說(shuō)明它遇到了第一個(gè)比自己大的元素，這樣下來(lái)，不難理解這個(gè)思路：
for 元素 in 列表:
while 棧不為空 and 棧頂元素 < 元素：
x = 出棧
找到了第一個(gè)比 x 大的元素，更新下標(biāo)
入棧
翻譯成代碼就是：
input = [5,3,1,2,4]
def find_first_greater(input: list) -> list:
# ans 保存結(jié)果，初始化為 -1
ans = [-1] * len(input)
# 模擬遞增棧，存放元素的下標(biāo)，為了計(jì)算距離
stack = []
for index, num in enumerate(input):
while stack and input[stack[-1]] < num:
x = stack.pop()
ans[x] = index - x
stack.append(index)
return ans
print(find_first_greater(input))
# output [-1, 3, 1, 1, -1]
有同學(xué)會(huì)問(wèn)了，for 循環(huán) + while 循環(huán)，這時(shí)間復(fù)雜度不還是 O(N^2) 嗎？其實(shí)不然，雖然有 while 循環(huán)，但是從整體來(lái)看共有 n 個(gè)元素，每個(gè)元素都被 push 入棧了一次，而最多會(huì)被 pop 一次，沒(méi)有任何冗余操作。所以總的計(jì)算規(guī)模是和元素規(guī)模 n 成正比的，也就是 O(n) 的復(fù)雜度。
做的多了，就可以總結(jié)出這樣的套路：
for 元素 in 列表:
while 棧不為空 and 棧頂元素（大于或者小于）目標(biāo)值：
出棧
根據(jù)業(yè)務(wù)處理
入棧
單調(diào)棧主要解決以下問(wèn)題：
尋找下一個(gè)更大元素 尋找前一個(gè)更大元素 尋找下一個(gè)更小元素 尋找前一個(gè)更小元素 qualified 的 窗口的 max/min sliding window max/min
實(shí)戰(zhàn)
1、循環(huán)數(shù)組找最大元素
解法：
# coding: utf-8
class Solution(object):
def nextGreaterElements(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums:
return list()
# 因?yàn)槭茄h(huán)數(shù)組，這里直接采用擴(kuò)容的方式，當(dāng)然也可以直接通過(guò)取模在處理
nums2 = nums * 2
# 單調(diào)遞增棧：用于找到下一個(gè)更大的元素
stack = [(0, nums2[0])]
# 維護(hù)元素的下一個(gè)更大元素
# 這里采用數(shù)組的形式
next_g = [-1] * len(nums2)
for index in range(1, len(nums2)):
num = nums2[index]
while stack and stack[-1][1] < num:
origin_index, _ = stack.pop()
# 通過(guò)原元素的索引來(lái)保存下一個(gè)更大元素
next_g[origin_index] = num
# 將原元素的索引保存下來(lái)
stack.append((index, num))
return next_g[:len(nums)]
2、接雨水
解法：
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if not height:
return 0
# 單調(diào)遞減棧
stack = list()
rst = 0
for index in range(len(height)):
h = height[index]
# 只要找到一個(gè)比棧頂元素大的元素, 說(shuō)明有可能形成了一個(gè)凹型
while stack and height[stack[-1]] < h:
# 凹型的右邊
right_slide = stack.pop()
if stack:
# 棧里面還存在元素，說(shuō)明形成了一個(gè)凹型，可以計(jì)算一個(gè)容量了：最低的高度 * 寬
rst += (min(height[stack[-1]], h) - height[
right_slide]) * (index - stack[-1] - 1)
stack.append(index)
return rst
3、股票價(jià)格跨度
解法：
class StockSpanner(object):
def __init__(self):
# 單調(diào)遞減棧：存放元素及其跨度
self.prices = list()
def next(self, price):
"""
:type price: int
:rtype: int
"""
rst = 1
while self.prices and self.prices[-1][1] <= price:
# 找到了一個(gè)遞增對(duì)，將其出棧（因?yàn)槠錃v史跨度已經(jīng)記錄在了下一個(gè)元素中），并將其跨度疊加
rst += self.prices.pop()[0]
# 保持元素及其跨度，便于下一次直接計(jì)算歷史跨度
self.prices.append((rst, price))
return rst
最后
單調(diào)棧是一種理解起來(lái)很容易，但是運(yùn)用起來(lái)并不那么簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。如果遇到的問(wèn)題，和前后元素之間的大小關(guān)系有關(guān)系的話，可以嘗試使用單調(diào)棧，也有不少問(wèn)題需要先轉(zhuǎn)換為求下一個(gè)最大/小元素的問(wèn)題，然后再使用單調(diào)棧解決。本文分享了單調(diào)棧的定義，套路，典型實(shí)戰(zhàn)案例，如果有幫助，請(qǐng)點(diǎn)贊、在看、關(guān)注支持，這次一定。
關(guān)注「Python七號(hào)」每天學(xué)習(xí)一個(gè)小技術(shù)