簡(jiǎn)述
由于棧有后進(jìn)先出的特性，利用好棧的這一特性，可以輕松解決一些看似復(fù)雜的問(wèn)題。
例題目錄
例題
1、最長(zhǎng)有效括號(hào)
題目描述：
給定一個(gè)只包含 '(' 和 ')' 的字符串，找出最長(zhǎng)的包含有效括號(hào)的子串的長(zhǎng)度。
示例 1:
輸入: "(()"
輸出: 2
解釋: 最長(zhǎng)有效括號(hào)子串為 "()"
算法
維護(hù)一個(gè)棧，初始狀態(tài)下放入 -1，遍歷字符串
“(”時(shí)， 入棧，
“)”時(shí)， 彈出棧頂，如果此時(shí)?？眨霔?；不為空，計(jì)算 i - stack[-1]
代碼
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1]
res = 0
for i, char in enumerate(s):
if char == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
res = max(res, i - stack[-1])
return res
時(shí)間復(fù)雜度：O(n)
這個(gè)問(wèn)題也可以用動(dòng)態(tài)規(guī)劃來(lái)解決。參考
2、逆波蘭表達(dá)式求值
題目描述：
根據(jù)逆波蘭表示法，求表達(dá)式的值。
有效的運(yùn)算符包括 +, -, *, / 。每個(gè)運(yùn)算對(duì)象可以是整數(shù)，也可以是另一個(gè)逆波蘭表達(dá)式。
說(shuō)明：
整數(shù)除法只保留整數(shù)部分。
給定逆波蘭表達(dá)式總是有效的。換句話說(shuō)，表達(dá)式總會(huì)得出有效數(shù)值且不存在除數(shù)為 0 的情況。
示例 1：
輸入: ["2", "1", "+", "3", "*"]
輸出: 9
解釋: ((2 + 1) * 3) = 9
算法：
維護(hù)一個(gè)棧，遇到數(shù)字入棧，遇到符號(hào)彈出兩個(gè)數(shù)字計(jì)算后的值再入棧，最后棧中所剩的數(shù)就是結(jié)果。
代碼
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token == '/':
v1 = stack.pop()
v2 = stack.pop()
stack.append(int(v2 / v1))
elif token == '-':
v1 = stack.pop()
v2 = stack.pop()
stack.append(v2 - v1)
elif token == '+':
v1 = stack.pop()
v2 = stack.pop()
stack.append(v2 + v1)
elif token == '*':
v1 = stack.pop()
v2 = stack.pop()
stack.append(v2 * v1)
else:
stack.append(int(token))
return stack[-1]
時(shí)間復(fù)雜度：O(n)
