單調(diào)棧

• 單調(diào)棧是一個棧，里面的元素的大小按照它們所在棧的位置，滿足一定的單調(diào)性；

• 性質(zhì)：

  • 單調(diào)遞減棧能找到左邊第一個比當(dāng)前元素大的元素；
  • 單調(diào)遞增棧能找到左邊第一個比當(dāng)前元素小的元素；

• 應(yīng)用場景

  • 一般用于解決第一個大于XXX或者第一個小于XXX這一類的題目

• 優(yōu)點(diǎn)：實(shí)踐復(fù)雜度是線性的，每個元素只遍歷一次
  

• 單調(diào)遞減棧，每次都能找到左邊第一個比它大的數(shù)

• 單調(diào)遞增棧，每次都能找到左邊第一個比它小的數(shù)

84. 柱狀圖中最大的矩形

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

解法一：暴力解法

依次遍歷柱形的高度，對于每一個高度分別向兩邊擴(kuò)散，求出當(dāng)前高度為矩形的最大寬度

• 向左遍歷，看最多能向左延伸多長，找到大于等于當(dāng)前柱形高度的最左邊元素的下標(biāo)；
• 向右遍歷，看最多能向右延伸多長，找到大于等于當(dāng)前柱形高度的最右邊元素的下標(biāo)；
• 計算當(dāng)前高度對應(yīng)的最大面積，與歷史最大值進(jìn)行比較并更新。

該解法在用例數(shù)量過多時，容易超出實(shí)時間限制

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:size = len(heights)res = 0for i in range(size):# 找左邊最后一個大于等于heights[i]的下標(biāo)left = icur_height = heights[i]while left > 0 and heights[left-1] >= cur_height:left -= 1# 找右邊最后一個大于等于heights[i]的下標(biāo)right = iwhile right < size-1 and heights[right + 1] >= cur_height:right += 1max_width = right - left + 1res = max(res, max_width * cur_height)return res

解法二：單調(diào)棧

• 獲取每根柱子左邊第一個比它低的柱子坐標(biāo)，（單調(diào)遞增棧）
• 獲取每根柱子右邊第一個比它低的柱子下標(biāo)，（倒序來做，就是左邊第一個比它低的柱子）
• 遍歷每根柱子求最大面積
• 哨兵技巧：兩邊各添加一個虛擬柱子

class Solution:def largestRectangleArea(self, heights: List[int]) -> int:stack = []left = [0 for _ in range(len(heights))]right = [0 for _ in range(len(heights))]res = 0# 獲取每根柱子左邊第一個比它低的柱子下標(biāo)for i in range(len(heights)):while stack and heights[stack[-1]] >= heights[i]:stack.pop()if not stack:left[i] = -1else:left[i] = stack[-1]stack.append(i)stack = []# 獲取每根柱子右邊第一個比它低的柱子下標(biāo)for j in range(len(heights) - 1, -1, -1):while stack and heights[stack[-1]] >= heights[j]:stack.pop()if not stack:right[j] = len(heights)else:right[j] = stack[-1]stack.append(j)# 求最大面積for i in range(len(heights)):res = max(res, heights[i] * (right[i] - left[i] - 1))return res

• 單調(diào)棧圖示：（獲取每根柱子右邊第一個比它低的柱子下標(biāo)，則需要倒序來做）
  

附錄基礎(chǔ)

python數(shù)據(jù)結(jié)構(gòu)與算法理論基礎(chǔ)（專欄）

數(shù)據(jù)結(jié)構(gòu)與算法（python）http://t.csdnimg.cn/Gb6MN

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法；而且在面試過程中這些是必考，必問的內(nèi)容。內(nèi)容大綱：基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)（樹、鏈表、棧、隊列等）、常見算法（排序算法、遞歸算法等）。

專欄是基于python的基礎(chǔ)知識，是很好的入門學(xué)習(xí)資料。幫助大家快速理解這些數(shù)據(jù)結(jié)構(gòu)和常見算法的概念，同時結(jié)合力扣題目，也能更好的掌握這些知識，達(dá)到在面試中游刃有余的效果。

python基礎(chǔ)語法

python基礎(chǔ)精講 http://t.csdnimg.cn/HdKdi

本專欄主要針對python基礎(chǔ)語法，幫助學(xué)習(xí)者快速接觸并掌握python大部分最重要的語法特征。
1、基本數(shù)據(jù)類型和變量
2、分支結(jié)構(gòu)與循環(huán)結(jié)構(gòu)
3、函數(shù)與異常處理
4、類與模塊
5、文件讀寫

通過本專欄可以快速掌握python的基礎(chǔ)語法。