所有題目均來自于LeetCode，刷題代碼使用的Python3版本

單調(diào)棧

通常針對一維數(shù)組的問題，如果需要尋找一個元素右邊或者左邊第一個比自己大或者小的元素的位置，就可以使用單調(diào)棧，時間復雜度為O(n)

單調(diào)棧的本質(zhì)是空間換時間， 遍歷的過程中需要使用一個棧記錄右邊第一個比當前元素高的值。優(yōu)點是整個數(shù)組只需要遍歷一次。

使用單調(diào)棧需要明確的幾點：

• 單調(diào)棧中存放的元素是什么？
• 單調(diào)棧里的元素是遞增還是遞減？

單調(diào)棧中的元素可以是遞增的也可以是遞減的，具體需要看題目的需求。

單調(diào)棧中存放的元素最好是下標，這樣具有更好的泛型

練習題

739、每日溫度

使用單調(diào)棧的方式從前往后進行遍歷；

棧中的元素從棧底到棧頂對應下標的值是遞減的，直到找到一個比棧頂元素大的值，然后出棧。

棧中存放的是元素的下標，如果出現(xiàn)一個新的元素比棧中元素都要大的時候，就對棧中元素進行循環(huán)遍歷，將其對應的res值修改為當前元素的下標和棧中存放的值的差值，這就是最終結果，到最后一個元素的時候，因為初始化結果列表中元素值都是0，故不需要進行修改。

初始化答案res為全0的列表，這樣可以防止后面的元素沒有下一個更大的元素，當然這一點要根據(jù)題目的要求來，因為有些題目會賦值為-1。

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:res = [0] * len(temperatures)st = []# 從前往后進行遍歷for index, temp in enumerate(temperatures):# st不為空且溫度大于棧頂元素while st and temperatures[st[-1]] < temp:j = st.pop()# 題目中問的是下一個更高溫度出現(xiàn)在幾天之后 因此用下標之差表示即可res[j] = index - jst.append(index)return res

496、下一個更大元素I

直接尋找

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:res = [-1]*len(nums1)# 尋找下一個更大的元素for index,n1 in enumerate(nums1):startindex = nums2.index(n1)for n in nums2[startindex+1:]:if n>n1:res[index] = nbreakreturn res

使用單調(diào)棧

題目中有**【需要尋找最近一個比其大的元素】** 這樣的字眼，就可以使用 【單調(diào)棧】

本題需要注意的是題目中存在兩個數(shù)組，尋找第一個數(shù)組在第二個數(shù)組元素中下一個比對應元素大的元素。題目中說了兩個數(shù)組中是沒有重復元素的，可以采用單調(diào)棧+哈希表的方式進行解決。

單調(diào)棧解決的是nums2中每個元素對應的下一個比其大的元素

哈希表解決的是用來存儲每個元素對應的下一個元素值，這樣方便對nums1進行遍歷時的查找

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:st = []res = [-1]*len(nums2)for index,num in enumerate(nums2):# print(index,num)while st and nums2[st[-1]]<num:j = st.pop()res[j] = numst.append(index)# 使用zip通過兩個可迭代的對象構造字典myhash = dict(zip(nums2,res))ans = []for n1 in nums1:ans.append(myhash[n1])return ans

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:myhash = {}st = []res = []for index, n in enumerate(nums2):while st and nums2[st[-1]] < n:myhash[nums2[st.pop()]] = nst.append(index)for n1 in nums1:res.append(myhash.get(n1, -1))return res

503、下一個更大元素II

出現(xiàn)這種需要循環(huán)才能判斷的情況，可以采用求余數(shù)的方法來多遍歷一次。

類似的思路還有打家劫舍II中頭尾不能同時偷的情況，就可以采用將數(shù)組（列表）進行拆分：0-n-1和1-n的情況

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:# 如何解決循環(huán)的問題？# 循環(huán)也就最多循環(huán)一輪到自己本身# 用求余來表示res = [-1] * len(nums)st = []for index, n in enumerate(nums * 2):while st and nums[st[-1]] < n:res[st.pop()] = nst.append(index % len(nums))return res

42、接雨水

在做本題之前，需要明確計算的方法是按照行進行計算還是按照列進行計算，這兩個計算方法的不同會導致不同的做法。

按照行去計算的做法如下所示：逐行進行累加

按照列去計算的做法如下所示：逐列進行累加

按照列去計算的時候可以假設每一列的寬度為1，只需要逐列去進行累加即可得到最終結果，這個思路也衍生了下面的暴力算法：

• 暴力算法【逐列累加】

暴力算法的思路是一列一列的去記錄能夠裝的雨水是多少，最終累加起來。

記錄每個節(jié)點左邊和右邊的最大高度，然后用兩個最大高度中的最小值減去當前高度，然后乘以寬度1，將這個值累加到res中。

s = (min(lHeight,rHeight)-height[i]) * 1

當遍歷到第一個柱子和最后一個柱子的時候，不需要計算面積。對于其余的柱子，需要尋找其左邊和右邊的最高的柱子，然后取兩者中的最小值，用最小值的高度減去height[i]，得到差值就是可以裝的雨水的高度，然后用這個高度再乘以寬度1，就是能裝的雨水的體積。最后一直累加這個和，得到能裝的最多的雨水。

lHeight = height[i]
rHeight = height[i]
for j in range(i + 1, len(height)):rHeight = max(rHeight, height[j])
for j in range(i - 1, -1, -1):lHeight = max(lHeight, height[j])
res += min(lHeight, rHeight) - height[i]

很不幸代碼超時了。

class Solution:def trap(self, height: List[int]) -> int:# 暴力算法（從前往后進行遍歷）記錄當前位置左右的最高點res = 0for i in range(1, len(height) - 1):lHeight = height[i]rHeight = height[i]for j in range(i + 1, len(height)):rHeight = max(rHeight, height[j])for j in range(i - 1, -1, -1):lHeight = max(lHeight, height[j])res += min(lHeight, rHeight) - height[i]# print(i,lHeight,rHeight   res += min(lHeight, rHeight) - height[i]return res

• 雙指針【逐列累加】

在暴力算法中，每輪循環(huán)都需要重復去尋找當前位置左右更高的高度，可以采用雙指針的方法進行優(yōu)化：

注意：雙指針方法和暴力算法本質(zhì)上都是逐列進行累加的。

通過兩個單獨的for循環(huán)，得到lHeight和rHeight數(shù)組（分別表示每個柱子左右兩側(cè)的最高的高度是多少），然后在通過一次循環(huán)，從1遍歷到n-2位置的柱子，然后累加最終能夠裝的雨水的體積。

這里需要注意在循環(huán)的時候，需要進行賦初始值，例如找左側(cè)最大值的時候，下標為0的地方賦初值height[0]不需要進行比較，然后從下標1到n-1進行遍歷。具體的可以參考下圖

rHeight = [0] * n
lHeight = [0] * n
# 計算每個柱子左側(cè)的最高高度
lHeight[0] = height[0]
for i in range(1, n - 1):lHeight[i] = max(lHeight[i - 1], height[i])
# print(lHeight)
rHeight[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):rHeight[i] = max(rHeight[i + 1], height[i])

找到左邊和右邊的最高值，計算一列可以裝的水有多少

記錄每個柱子左邊的最高高度和右邊的最高高度，然后高度就是min(左邊最高高度，右邊最高高度)-height[i]，寬度就是1

class Solution:def trap(self, height: List[int]) -> int:# 雙指針n = len(height)if n<=2:return 0res = 0lheight = [0]*nrheight = [0]*nlheight[0] = height[0]   # 進行初始化for i in range(1,n-1):lheight[i] = max(lheight[i-1],height[i])rheight[n-1] = height[n-1] # 進行初始化for i in range(n-2,-1,-1):rheight[i] = max(rheight[i+1],height[i])# print(lheight,rheight)for i in range(1,n-1):res += min(lheight[i],rheight[i])-height[i]return res

• 單調(diào)?！局鹦欣奂印?/h4>

單調(diào)棧的核心思路是逐行進行累加

單調(diào)棧的思路就是如果棧為空，則先第一個柱子入棧，緊接著如果第二個柱子的高度低于棧中柱子的高度，則繼續(xù)入棧。也就是說此時棧中的元素從棧頂?shù)綏５资?strong>從小到大的順序。只有從小到大的順序才能夠再下一次遇到一個比棧頂元素高的柱子的時候形成一個凹槽，然后計算能夠裝的雨水的體積是多少。

如果遇到相同高度的柱子，這時我們需要保存的是最新的下標，這里需要將原來的棧頂元素pop彈出，然后將當前的下標i放到棧頂中。

如果出現(xiàn)一種情況是當前遍歷的高度高于棧頂元素的高度，那么彈出棧頂元素，此時如果棧不為空，則開始計算雨水。此時的棧頂?shù)脑氐母叨染褪前疾鄣母叨?#xff0c;當前遍歷的就是凹槽右邊的高度，然后棧頂?shù)南乱粋€元素就是左側(cè)的較高的柱子。right-left-1就是寬度，乘以min(left,right)-height[i]就是最終的面積。

這里詳細解釋一下面積計算的方法：長×高

長 = 當前遍歷的下標位置 - 左側(cè)最高高度下標位置 - 1

高 = min(左側(cè)最高高度，右側(cè)最高高度) - 當前柱子高度，具體體現(xiàn)為當前遍歷元素為右側(cè)最高高度，棧頂?shù)脑貫榘疾厶幍母叨?#xff0c;棧頂?shù)南乱粋€元素為左側(cè)最高高度。

例如下面這張圖中，當我遍歷到位置5的時候，其計算其長度應該5-1-1=3，然后高度為min(3,2)-1 = 1，所以面積就是3*1=3?？梢钥闯鰜磉@一行的面積確實就是3，符合我們的計算公式。

具體的分為下面三種情況：

• 當前遍歷的柱子的高度低于棧頂元素的高度，則繼續(xù)入棧；
• 當前遍歷的柱子的高度等于棧頂元素的高度，則將棧頂元素彈出，更新最新柱子高度，將新的柱子下標入棧；
• 當前遍歷的柱子的高度大于棧頂元素的高度，此時形成凹槽了，就計算雨水的面積了。

class Solution:def trap(self, height: List[int]) -> int:st = []res = 0for index, h in enumerate(height):while st and height[st[-1]] < h:j = st.pop()if st:res += (index - st[-1] - 1) * (min(h, height[st[-1]]) - height[j])if st and height[st[-1]] == h:st.pop()st.append(index)return res

84、柱狀圖中最大的矩形

• 暴力解法

在暴力解法中，從每個下標i位置出發(fā)，找到左右兩側(cè)比其高的位置，但是一旦出現(xiàn)比其低的位置直接break，記錄下左右下邊left和right，然后用right-left-1作為底面寬度，height[i]作為高度，得到最終的面積。將這個面積與sum_進行比較，取兩者中的最大值。

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:# 暴力解法sum_ = 0for i in range(len(heights)):left, right = i, iwhile left >= 0:if heights[left] < heights[i]:breakleft -= 1while right < len(heights):if heights[right] < heights[i]:breakright += 1sum_ = max(sum_, (right - left - 1) * heights[i])return sum_

• 雙指針法

記錄每個柱子左邊的第一個小于該柱子的下標，而不是記錄左邊第一個小于該柱子的高度

雙指針的難點就在于如何去尋找當前位置i的左右兩側(cè)第一個比其低的柱子的下標

此部分的代碼如下：

這里在尋找的時候需要進行初始化，不然的話while循環(huán)可能死循環(huán)。

注意這里如果minLeftIndex數(shù)組中元素值為-1或者minRightIndex數(shù)組中元素值為len(heights)表示該柱子左邊或者右邊沒有比其更矮的柱子，此時就以這個柱子的高度乘以寬度即可。

minLeftIndex[0] = -1
for i in range(1,n):t = i-1while t>=0 and heights[t]>=heights[i]:t = minLeftIndex[t]  # 左移minLeftIndex[i] = t
# print(minLeftIndex)
minRightIndex[n-1] = n
for i in range(n-2,-1,-1):t = i+1while t<=n-1 and heights[t]>=heights[i]:t = minRightIndex[t]minRightIndex[i] = t

完整代碼如下：

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:# 雙指針法n = len(heights)minLeftIndex = [0]*nminRightIndex = [0]*n# 尋找左邊的小于他的下標minLeftIndex[0] = -1for i in range(1,n):t = i-1while t>=0 and heights[t]>=heights[i]:t = minLeftIndex[t]  # 左移minLeftIndex[i] = t# print(minLeftIndex)minRightIndex[n-1] = nfor i in range(n-2,-1,-1):t = i+1while t<=n-1 and heights[t]>=heights[i]:t = minRightIndex[t]minRightIndex[i] = t# print(minRightIndex)res = 0for i in range(n):res = max(res,(minRightIndex[i]-minLeftIndex[i]-1)*heights[i])return res

• 單調(diào)棧法

在接雨水一題中，我們想要實現(xiàn)的效果是尋找到一個凹槽，即找到一個柱子左右兩側(cè)高于該柱子的柱子，然后逐行求面積。而本題所需要實現(xiàn)的效果是尋找一個柱子左右兩側(cè)低于該柱子的柱子。

單調(diào)棧中的順序（從棧頂?shù)綏５?/strong>）應該是從大到小的。這樣就方便找到每個節(jié)點的左邊或者右邊低于其高度的柱子。當遍歷到下一個柱子的高度小于棧頂元素的時候，就可以進行彈出了。在彈出的時候計算高度即可得到最終的答案。

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:# 單調(diào)棧heights.insert(0,0)heights.append(0)stack = [0]res = 0for i in range(1,len(heights)):if heights[i]>heights[stack[-1]]:stack.append(i)elif heights[i]==heights[stack[-1]]:stack.pop()stack.append(i)else:while stack and heights[i] < heights[stack[-1]]:mid = stack.pop()if stack:left_index = stack[-1]right_index = iwidth = right_index - left_index - 1height = heights[mid]res = max(res,width*height)stack.append(i)return res

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights.append(0)heights.insert(0,0)st = []res = 0for index,h in enumerate(heights):while st and h<heights[st[-1]]:# 開始進行計算面積mid = st.pop()if st:left = st[-1]right = indexres = max(res,heights[mid]*(right-left-1))if st and heights[st[-1]]==h:st.pop()st.append(index)return res

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:heights.insert(0, 0)heights.append(0)# print(heights)st = []res = 0for index in range(len(heights)):while st and heights[st[-1]] > heights[index]:# 計算面積j = st.pop()if st:res = max(res, (index - st[-1] - 1) * heights[j])if st and heights[st[-1]] == heights[index]:st.pop()st.append(index)return res

class Solution:def canSeePersonsCount(self, heights: List[int]) -> List[int]:n = len(heights)ans = [0]*nst = []for i in range(n-1,-1,-1):while st and st[-1]<heights[i]:st.pop()ans[i]+=1if st:ans[i]+=1st.append(heights[i])return ans