栈类型的题目在计算机课程中介绍得相当多，网上的文章同样也不少，很多问题可以用栈以经典的方式解决。这里我简单总结一下这段时间做的关于stack的leetcode题目。
'栈'的特性：可存下数据，稍后进行运算
下面的问题可以用stack来解决：
- 括号匹配问题
- 编码问题
- 表达式，逆波兰表达式
- 回溯，迷宫
- 数制转换
- 单调递增/减
这里参考了清华的《数据结构》严然敏教材与网上的一个博客。
模板
单调递增/减类题目
这类题目用了一个stack存放沿路scan的元素，把元素和元素的位置存在stack中(很类似Hash Table的用法,key=element, value=position)，然后用栈顶元素与新扫描的元素进行比较。
stack = []
for num in nums:
# Check if stack is empty
# Check top element of stack
# add
在stack中存放tuple = (数字/字母, 位置)是这类题目特点。
比如739. Daily Temperatures 这一题，我的代码如下：
from collections import deque
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
stack = deque()
ret = []
for i, temp in enumerate(T):
ret.append(0)
while stack and stack[-1][1] < temp:
j, _ = stack.pop()
ret[j] = i-j
stack.append((i, temp))
# print('s:', stack)
# print('r:', ret)
return ret
- Next Greater Node In Linked List
这题一开始不会做，借鉴了网上人的智慧。
class Solution:
def nextLargerNodes(self, head: ListNode) -> List[int]:
if not head:
return []
if not head.next:
return [0]
cur = head
stack, res = [], []
index = 0
while cur:
# peek = stack[-1]
while len(stack) > 0 and stack[-1][0] < cur.val:
peek = stack.pop()
res.append((peek[1], cur.val))
stack.append((cur.val, index))
index, cur = index+1, cur.next
while len(stack) > 0:
top = stack.pop()
res.append((top[1], 0))
result = [0] * len(res)
for tup in res:
result[tup[0]] = tup[1]
return result
- Next Greater Element II
基本跟上面的1019一个模子出来，除了那些找不到下一个greater的数字可以循环找之外，其他基本一样。这里利用了stack做这点的特点，在第一遍找不到下一个greater number的number一定都被留在stack中，只要把他们全都pop出来，在nums中找一下就好。
from collections import deque
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
stack = deque()
ret = []
for index, num in enumerate(nums):
# traverse
# 0th to do: init ret by adding 0
ret.append(0)
# 1st to do: check stack
while stack and stack[-1][1] < num:
# if top element of stack < number during traversing
i, _ = stack.pop()
ret[i] = num
# 2nd to do: move cursor to next
stack.append((index, num))
print('s:', stack)
print('r:', ret)
while stack:
i, val = stack.pop()
for num in nums:
if val < num:
ret[i] = num
break
else:
ret[i] = -1
print('r:', ret)
return ret
把以上题目的思路放到hard题 42. Trapping Rain Water中，也是有用的。Trapping Rain Water题目意思是去找"坑"，而"坑"该怎么定义呢：
假设height存有[0,...,n-1]个height, 一个height[I]是"坑"trap要满足：height[I]两边都有next greater number。
Trapping Rain Water
如果用list [0,1,0,2,1,0,1,3,2,1,2,1]表示上面的图，那么我们会发现三片trap，[0,1,0,2,1,0,1,3,2,1,2,1]，即[2th]，[4th，5th，6th]，[9th]元素都出现小于两边元素的情况。利用739. Daily Temperatures 或1019的思路：
- 从左到右，得到一个next greater height, next1[]
- 从右到左，得到另一个next greater height, next_2[]
- 假如ith个height，即height[I]，在next1[], next2[]中都存在元素，那么height[I]就是个"坑"。
以上面的height为例，next1 = [1, 2, 2, 3, 3, 1, 3, 0, 0, 2, 0, 0], next2=[0, 0, 1, 0, 2, 1, 2, 0, 3, 2, 3, 2]。
找到"坑"之后，接下来要算坑能装多少水。这里我曾犯了错误，让能装的水=min{next greater number from next1 and next2} - i th height。也就是说假如i th height是个坑，那么从next1, next 2中找到较小的那个greater number，然后减去第i个 height，得到能装的水量。这里选择较小的那个greater number是如果有短板，水位跟定只能跟短板。这样算错的地方在于，假如有好几个坑连成一起，那么他们的"短板"是几个坑的短板中最大的那个。
这里是根据如上思路的代码：
class Solution:
def trap(self, height: List[int]) -> int:
def nextGreater(nums):
stack, res = [], []
for i, num in enumerate(nums):
res.append(0)
while stack and stack[-1][1] < num:
res[stack.pop()[0]] = num
stack.append((i, num))
return res
next_l_r = nextGreater(height)
next_r_l = nextGreater(height[::-1])
water, next_r_l = 0, next_r_l[::-1]
print(next_l_r)
print(next_r_l)
peak, trap = 0, []
for i, num in enumerate(height):
if next_l_r[i] and next_r_l[i]:
tmp = next_l_r[i] if next_l_r[i] < next_r_l[i] else next_r_l[i]
peak = peak if tmp < peak else tmp
trap.append(num)
else:
while trap:
water += peak - trap.pop()
peak = 0
return water
表达式问题
我只做了一个，就是150. Evaluate Reverse Polish Notation。题目其实比教科书里的逆波兰表达式还简单些，没有括号之类的运算符。一个栈存数字，遇到运算符直接结算并把结果压入栈。
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
if not tokens:
return 0
stack = []
def RepresentsInt(s):
try:
int(s)
return True
except ValueError:
return False
for token in tokens:
# print(token)
if RepresentsInt(token):
stack.append(int(token))
else:
a = stack.pop()
b = stack.pop()
res = 0
if token == '+':
res = b + a
elif token == '-':
res = b - a
elif token == '/':
res = int(b/a)
elif token == '*':
res = b * a
stack.append(res)
print("{}{}{}={}".format(b,token,a,res))
return stack.pop()
之后如果遇到其他有趣的stack题目，会持续更新在这里。
网友评论