互联网招聘网站,express做静态网站,浙江省两学一做网站,昆山便宜做网站栈是先入后出#xff08;后入先出#xff09;的数据结构#xff0c;常用操作就 push 和 pop#xff0c;Python中用列表实现即可#xff0c;基本概念可以看Leetbook相关章节。
普通栈
232. 用栈实现队列
class MyQueue:def __init__(self):self.stack1 []self.stack2 …栈是先入后出后入先出的数据结构常用操作就 push 和 popPython中用列表实现即可基本概念可以看Leetbook相关章节。
普通栈
232. 用栈实现队列
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两个栈用 stack1 来存放 push 进来的数当要 pop 的时候借助 stack2 把最左边的数 pop 出去相当于 popleft然后再把剩余的数放回 stack1由于需要判断空所以用一个 size 大小来记录。
155. 最小栈剑指 Offer 30. 包含min函数的栈
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]实现最小栈的关键就是要用辅助栈记录每次 push 操作时的最小值这样栈值在递增时最小值永远是第一个值如 [1, 2, 3, 4] 对应 [1, 1, 1, 1]在递减时最小值永远是当前值如 [4, 3, 2, 1] 对应 [4, 3, 2, 1]。
1047. 删除字符串中的所有相邻重复项
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)栈的最重要的应用就是匹配这是由它后入先出的性质所决定的。
20. 有效的括号
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首先判断长度若为奇数必然不能匹配直接返回 False。然后分类讨论如果是三个左括号之一就 push 进入栈如果是三个右括号之一就检查栈顶若栈顶为空就肯定不匹配不为空则考察弹出的栈顶元素若不是对应的左括号则返回 False。最后如果还有左括号栈非空也返回 False。
227. 基本计算器 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[index1].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)这题与上一个的括号题类似也是分类讨论。如果遇到空格则跳过如果遇到符号则记录下来如果遇到数字则根据其前面的符号来进行相应的运算。这里用 while 循环是因为要处理多位数字的情况如 42 这种数在遇到符号前都将其作为一个数而不是 4 和 2 两个数。
150. 逆波兰表达式求值
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()仿照上一题的写法同样是分类讨论字符是数字的话就入栈是运算符的话就让两个操作数出栈进行运算后把结果再入栈。由于这题多位数是直接给出来了的所以可以用 for 循环而不是 while 循环如下所示
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. 验证栈序列剑指 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 序列然后逐个把 pushed 序列的元素 push 进入栈中如果出现相同值则弹出栈顶元素同时指针右移1位如果所有元素都能pop 则返回 True。
单调栈
496. 下一个更大元素 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利用单调栈和字典记录下 nums2 中每个元素右边第一个比自己大的元素然后遍历 nums1 从字典找相应答案即可。
503. 下一个更大元素 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通过循环 2n 次可以达到循环数组的效果但毕竟答案要的索引是 n 个所以通过对 n 取余来表示原数组的下标。
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遍历每一天的温度用一个栈记录每天的温度下标当遍历到第 i 天时比较第 i 天是否大于前面某天的温度如果是则弹出该天已找到答案并在 ans 数组中记录下天数差值。
316. 去除重复字母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)首先用字典记录下每个字符出现的次数然后从左往右遍历字符串。对于每一个字符如果它已经在单调递减栈里面了则不需要入栈直接次数减 1如果它不在栈里则判断栈顶元素是否可以出栈比当前字符大且不是剩下的唯一字符之后再将字符入栈。
