棧是先入后出（后入先出）的數(shù)據(jù)結(jié)構(gòu)，常用操作就 push 和 pop，Python中用列表實(shí)現(xiàn)即可，基本概念可以看Leetbook相關(guān)章節(jié)。

普通棧

232. 用棧實(shí)現(xiàn)隊(duì)列

class MyQueue:def __init__(self):self.stack1 = []self.stack2 = []self.size = 0def push(self, x: int) -> None:while self.stack2:self.stack1.append(self.stack2.pop())self.stack1.append(x)self.size += 1def pop(self) -> int:while self.stack1:self.stack2.append(self.stack1.pop())self.size -= 1ans = self.stack2.pop()while self.stack2:self.stack1.append(self.stack2.pop())return ansdef peek(self) -> int:return self.stack1[0]def empty(self) -> bool:return self.size == 0

兩個(gè)棧，用 stack1 來存放 push 進(jìn)來的數(shù)，當(dāng)要 pop 的時(shí)候，借助 stack2 把最左邊的數(shù) pop 出去（相當(dāng)于 popleft），然后再把剩余的數(shù)放回 stack1，由于需要判斷空，所以用一個(gè) size 大小來記錄。

155. 最小棧（劍指 Offer 30. 包含min函數(shù)的棧）

class MinStack:def __init__(self):self.stack = [(0, float('+inf'))]def push(self, x: int) -> None:self.stack.append((x, min(self.stack[-1][1], x)))def pop(self) -> None:self.stack.pop()def top(self) -> int:return self.stack[-1][0]def getMin(self) -> int:return self.stack[-1][1]

實(shí)現(xiàn)最小棧的關(guān)鍵就是要用輔助棧記錄每次 push 操作時(shí)的最小值，這樣棧值在遞增時(shí)，最小值永遠(yuǎn)是第一個(gè)值（如 [1, 2, 3, 4] 對(duì)應(yīng) [1, 1, 1, 1]）；在遞減時(shí)，最小值永遠(yuǎn)是當(dāng)前值（如 [4, 3, 2, 1] 對(duì)應(yīng) [4, 3, 2, 1]）。

1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng)

class Solution:def removeDuplicates(self, s: str) -> str:stack = []for ch in s:if stack and stack[-1] == ch:stack.pop()else:stack.append(ch)return ''.join(stack)

棧的最重要的應(yīng)用就是匹配，這是由它后入先出的性質(zhì)所決定的。

20. 有效的括號(hào)

class Solution:def isValid(self, s: str) -> bool:if len(s) % 2 == 1:return Falsestack = []for ch in s:if ch in ('(', '[', '{'):stack.append(ch)else:if len(stack) == 0:return Falsepre = stack.pop()if (pre == '(' and ch != ')') or (pre == '[' and ch != ']') or (pre == '{' and ch != '}'):return Falsereturn len(stack) == 0

首先判斷長度，若為奇數(shù)必然不能匹配，直接返回 False。然后分類討論：如果是三個(gè)左括號(hào)之一，就 push 進(jìn)入棧；如果是三個(gè)右括號(hào)之一，就檢查棧頂，若棧頂為空就肯定不匹配，不為空則考察彈出的棧頂元素，若不是對(duì)應(yīng)的左括號(hào)則返回 False。最后如果還有左括號(hào)（棧非空），也返回 False。

227. 基本計(jì)算器 II

class Solution:def calculate(self, s: str) -> int:stack = []size = len(s)index = 0op = '+'while index < size:if s[index] == ' ':index += 1continueif s[index] in '+-*/':op = s[index]elif s[index].isdigit():num = ord(s[index]) - ord('0')while index + 1 < size and s[index+1].isdigit():index += 1num = num * 10 + ord(s[index]) - ord('0')if op == '+':stack.append(num)elif op == '-':stack.append(-num) elif op == '*':top = stack.pop()stack.append(top * num)elif op == '/':top = stack.pop()stack.append(int(top / num))index += 1return sum(stack)

這題與上一個(gè)的括號(hào)題類似，也是分類討論。如果遇到空格則跳過；如果遇到符號(hào)則記錄下來；如果遇到數(shù)字，則根據(jù)其前面的符號(hào)來進(jìn)行相應(yīng)的運(yùn)算。這里用 while 循環(huán)是因?yàn)橐幚矶辔粩?shù)字的情況，如 42 這種數(shù)，在遇到符號(hào)前都將其作為一個(gè)數(shù)（而不是 4 和 2 兩個(gè)數(shù)）。

150. 逆波蘭表達(dá)式求值

class Solution:def evalRPN(self, tokens: List[str]) -> int:stack = []size = len(tokens)index = 0while index < size:if tokens[index] in '+-*/':second = stack.pop()first = stack.pop()if tokens[index] == '+':num = first + secondelif tokens[index] == '-':num = first - secondelif tokens[index] == '*':num = first * secondelif tokens[index] == '/':num = int(first / second)stack.append(num)index += 1else:stack.append(int(tokens[index]))index += 1return stack.pop()

仿照上一題的寫法，同樣是分類討論，字符是數(shù)字的話就入棧，是運(yùn)算符的話就讓兩個(gè)操作數(shù)出棧，進(jìn)行運(yùn)算后把結(jié)果再入棧。由于這題多位數(shù)是直接給出來了的，所以可以用 for 循環(huán)而不是 while 循環(huán)，如下所示：

class Solution:def evalRPN(self, tokens: List[str]) -> int:stack = []for token in tokens:if token == '+':stack.append(stack.pop() + stack.pop())elif token == '-':stack.append(-stack.pop() + stack.pop())elif token == '*':stack.append(stack.pop() * stack.pop())elif token == '/':stack.append(int(1/stack.pop()*stack.pop()))else:stack.append(int(token))return stack.pop()

946. 驗(yàn)證棧序列（劍指 Offer 31. 棧的壓入、彈出序列）

class Solution:def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:pop_pointer = 0stack = []for num in pushed:stack.append(num)while stack and pop_pointer < len(popped) and stack[-1] == popped[pop_pointer]:stack.pop()pop_pointer += 1return pop_pointer == len(popped)

用指針記錄 popped 序列，然后逐個(gè)把 pushed 序列的元素 push 進(jìn)入棧中，如果出現(xiàn)相同值，則彈出棧頂元素，同時(shí)指針右移1位，如果所有元素都能pop 則返回 True。

單調(diào)棧

496. 下一個(gè)更大元素 I

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:ans = []stack = []num_map = dict()for num in nums2:while stack and stack[-1] < num:num_map[stack[-1]] = numstack.pop()stack.append(num)for num in nums1:ans.append(num_map.get(num, -1))return ans

利用單調(diào)棧和字典記錄下 nums2 中每個(gè)元素右邊第一個(gè)比自己大的元素，然后遍歷 nums1 從字典找相應(yīng)答案即可。

503. 下一個(gè)更大元素 II

class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:n = len(nums)ans = [-1 for _ in range(n)]stack = []for i in range(n * 2):while stack and nums[i % n] > nums[stack[-1]]:index = stack.pop()ans[index] = nums[i % n]stack.append(i % n)return ans

通過循環(huán) 2n 次可以達(dá)到循環(huán)數(shù)組的效果，但畢竟答案要的索引是 n 個(gè)，所以通過對(duì) n 取余來表示原數(shù)組的下標(biāo)。

739. 每日溫度

class Solution:def dailyTemperatures(self, temperatures: List[int]) -> List[int]:n = len(temperatures)ans = [0 for _ in range(n)]stack = []for i in range(n):while stack and temperatures[stack[-1]] < temperatures[i]:index = stack.pop()ans[index] = i - indexstack.append(i)return ans

遍歷每一天的溫度，用一個(gè)棧記錄每天的溫度下標(biāo)，當(dāng)遍歷到第 i 天時(shí)，比較第 i 天是否大于前面某天的溫度，如果是則彈出該天（已找到答案），并在 ans 數(shù)組中記錄下天數(shù)（差值）。

316. 去除重復(fù)字母（1081. 不同字符的最小子序列）

class Solution:def removeDuplicateLetters(self, s: str) -> str:stack = []counter = collections.Counter(s)for ch in s:if ch not in stack:while stack and ch < stack[-1] and counter[stack[-1]] > 0:stack.pop()stack.append(ch)counter[ch] -= 1return ''.join(stack)

首先用字典記錄下每個(gè)字符出現(xiàn)的次數(shù)，然后從左往右遍歷字符串。對(duì)于每一個(gè)字符，如果它已經(jīng)在單調(diào)遞減棧里面了，則不需要入棧，直接次數(shù)減 1；如果它不在棧里，則判斷棧頂元素是否可以出棧（比當(dāng)前字符大且不是剩下的唯一字符），之后再將字符入棧。

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的栈的基础概念与经典题目（Leetcode题解-Python语言）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。