数据结构与算法—-复习Part 9 （堆栈与单调栈）
本系列是算法通关手册LeeCode的学习笔记
算法通关手册（LeetCode） | 算法通关手册（LeetCode） (itcharge.cn)
本系列为自用笔记，如有版权问题，请私聊我删除。
目录
一，堆栈（Stack）
简称为栈，是一种只允许在表的一端进行插入和删除操作的线性表。
把栈中允许插入和删除的一端称为 栈顶（top）；另一端称为 栈底（bottom）。当表中没有任何数据元素时，称之为空栈。
堆栈有【入栈】和【出栈】两种基本操作。
是一种【后进先出（LIFO，Last In First Out）】的线性表。
基本操作有：
初始化空栈：创建一个空栈，定义栈的大小 size，栈顶指针 top；
判断栈是否为空：为空，返回 True，否则返回 False。用于出栈和获取栈顶元素；
判断栈是否已满：已满，返回 True，否则返回 False。用于入栈；
入栈：在最后元素之后插入一个新的数据元素，并改变栈顶指针 top 的位置；
出栈：删除最后一个数据元素，并改变栈顶指针 top 的位置；
获取栈顶元素：获取最后位置的数据元素，不改变栈顶指针的位置。
堆栈的顺序存储
顺序栈即堆栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时使用指针 top 指示栈顶元素在顺序栈中的位置。
实现代码：
class Stack:
# 初始化空栈
def __init__(self, size = 100):
self.size = size
self.stack = []
self.top = -1
# 判断栈是否为空
def isEmpty(self):
return self.top == -1
# 判断栈是否已满
def isFull(self):
return self.top + 1 == self.size
# top 从 -1 开始
# 入栈操作
def push(self, value):
if self.isFull():
raise Exception('Stack if full.')
else:
self.stack.append(value)
self.top += 1
# 出栈操作
def pop(self):
if self.isEmpty():
raise Exception('Stack is empty.')
else:
self.stack.pop()
self.top -= 1
# 获取栈顶元素
def peek(self):
if self.isEmpty():
raise Exception('Stack is empty.')
else:
return self.stack[self.top]堆栈的链式存储
链式栈即堆栈的链式存储结构。利用单链表的方式来实现堆栈，栈中元素按照插入顺序依次插入到链表的第一个节点之前，top 指针永远指向链表的头节点位置。
实现代码：
class Node:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
class Stack:
# 初始化空栈
def __init__(self):
self.top = None
# 判断栈是否为空
def isEmpty(self):
return self.top == None
# 入栈操作
def push(self, value):
node = Node(value)
node.next = self.top
self.top = node
# 出栈操作
def pop(self):
if self.isEmpty():
raise Exception('Stack is empty.')
else:
cur = self.top
self.top = self.top.next
del cur
# 获取栈顶元素
def peek(self):
if self.isEmpty():
raise Exception('Stack is empty.')
else:
return self.top.val
例题
括号匹配是栈结构的经典应用；
首先查看 s 的长度是否为偶数；
使用栈结构，若是左括号则入栈，右括号且与栈顶匹配，则出栈；
若栈为空，则返回 True，否则返回 Fasle
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1:
return False
stack = list()
for ch in s:
if ch == '(' or ch == '[' or ch == '{':
stack.append(ch)
elif ch == ')':
if len(stack) !=0 and stack[-1] == '(':
stack.pop()
else:
return False
elif ch == ']':
if len(stack) !=0 and stack[-1] == '[':
stack.pop()
else:
return False
elif ch == '}':
if len(stack) !=0 and stack[-1] == '{':
stack.pop()
else:
return False
if len(stack) == 0:
return True
else:
return False
时间复杂度 O(n)
空间复杂度 O(1)
实现计算器是栈的经典应用；
将第一个数字入栈，从第二个数字 num 开始，数字前的符号记为 op；
若 op = + ，将 num 入栈，若 op = -，将 -num 入栈；
若 op = *，取出栈顶元素 top ，将 top * num 入栈；
若 op = / ，取出栈顶元素 top ，将 top // num 入栈；
对栈内所有元素求和。
class Solution:
def calculate(self, s: str) -> int:
size = len(s)
stack = []
op = '+'
index = 0
while index < size:
if s[index] == ' ':
index += 1
continue
if s[index].isdigit():
num = ord(s[index]) - ord('0')
while index + 1 < size and s[index+1].isdigit():
index += 1
num = 10 * num + 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))
elif s[index] in "+-*/":
op = s[index]
index += 1
return sum(stack)
时间复杂度 O(n)
空间复杂度 O(n)
二，单调栈（Monotone Stack）
一种特殊的栈。在栈 LIFO 的规则基础上，要求从栈顶到栈底的元素单调。
单调递增栈
只有比栈顶元素小的元素才能直接进栈，否则需要将栈中比当前元素小的元素出栈，再将当前元素入栈。
代码模板：
def monotoneIncreasingStack(nums):
stack = []
for num in nums:
while stack and num >= stack[-1]:
stack.pop()
stack.append(num)
单调递减栈
只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。
代码模板：
def monotoneDecreasingStack(nums):
stack = []
for num in nums:
while stack and num <= stack[-1]:
stack.pop()
stack.append(num)
例题
单调栈适用于从端点处找第一个大于标准数的元素。
nums1 是 nums2 的子集，且没有相同元素；
可以使用单调栈遍历 nums2，若当前元素大于栈顶元素，则记录当前元素入哈希表；
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
res = []
stack = []
num_map = dict()
for num in nums2:
while stack and num > stack[-1]:
num_map[stack[-1]] = num # 如 stack = [1, 3, 5] num = 4
# 元素 1 能入栈说明还没找到右侧比 1 大的元素
# 此时将元素 1 出栈，并记录 num_map[1] = 4
# 意为 比 1 大的第一个元素是4
stack.pop()
stack.append(num)
for num in nums1:
res.append(num_map.get(num, -1))
return res单调栈在使用时，应注意需要返回的元素是什么，以此为基础决定如何构造单调栈。
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
n = len(T)
stack = []
ans = [0 for _ in range(n)]
for i in range(n):
while stack and T[i] > T[stack[-1]]:
index = stack.pop()
ans[index] = (i-index)
stack.append(i)
return ans
算法通关手册（LeetCode） | 算法通关手册（LeetCode）
原文内容在这里，如有侵权，请联系我删除。