leetcode(2)栈

leetcode(2)栈"/>

leetcode(2)栈

leetcode 155 最小栈
stack相当于栈，先进后出 存储全部栈元素 [-3,2,-1]
min_stack,存储栈当前位置最小的元素 [-3,-3,-3]

class MinStack:def __init__(self):self.stack = []self.min_stack = [math.inf]def push(self, x: int) :self.stack.append(x)self.min_stack.append(min(x, self.min_stack[-1]))def pop(self) -> None:self.stack.pop()self.min_stack.pop() #  也需要删除当前位置的最小元素def top(self) -> int:return self.stack[-1]def getMin(self) -> int:return self.min_stack[-1]

leetcode 20 有效括号

class Solution:def isValid(self, s: str) -> bool:dic = {'{': '}',  '[': ']', '(': ')','?':'?'}stack = ["?"]for c in s:if c in dic: stack.append(c)elif dic[stack.pop()] != c: return False return len(stack) == 1

leetcode 227 基本计算器2

class Solution:def calculate(self, s: str) -> int:n = len(s)stack = []preSign = '+'num = 0for i in range(n):if s[i] != ' ' and s[i].isdigit():num = num * 10 + ord(s[i]) - ord('0')if i == n - 1 or s[i] in '+-*/':if preSign == '+':stack.append(num)elif preSign == '-':stack.append(-num)elif preSign == '*':stack.append(stack.pop() * num)else:stack.append(int(stack.pop() / num))preSign = s[i]num = 0return sum(stack)

leetcode 150 逆波兰表达式

class Solution:def evalRPN(self, tokens: List[str]) -> int:op_to_binary_fn = {"+": add,"-": sub,"*": mul,"/": lambda x, y: int(x / y),   # 需要注意 python 中负数除法的表现与题目不一致}stack = list()for token in tokens:try:num = int(token)except ValueError:num2 = stack.pop()num1 = stack.pop()num = op_to_binary_fn[token](num1, num2)finally:stack.append(num)return stack[0]

leetcode 验证栈序列
输入两个栈 A和B判断B是否为A的出栈序列
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

class Solution:def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:stack, i = [], 0for num in pushed:stack.append(num) # num 入栈while stack and stack[-1] == popped[i]: # 循环判断与出栈stack.pop()i += 1return not stack

leetcode 字符串编解码

class Solution:def decodeString(self, s: str) -> str:stack, res, multi = [], "", 0for c in s:if c == '[':stack.append([multi, res])res, multi = "", 0elif c == ']':cur_multi, last_res = stack.pop()res = last_res + cur_multi * reselif '0' <= c <= '9':multi = multi * 10 + int(c)            else:res += creturn res

leetcode 下一个更大元素

class Solution1:def nextGreaterElement(self, nums1, nums2):dic = {}for i in range(len(nums2)):j = i + 1while j < len(nums2) and nums2[i] >= nums2[j]:j += 1if j < len(nums2) and nums2[i] < nums2[j]:dic[nums2[i]] = nums2[j]return [dic.get(x, -1) for x in nums1]

leetcode 去除重复字符

class Solution(object):def removeKdigits(self, num, k):stack = []remain = len(num) - kfor digit in num:while k and stack and stack[-1] > digit:stack.pop()k -= 1stack.append(digit)return ''.join(stack[:remain]).lstrip('0') or '0'

leetcode 每日最高温度

class Solution:def dailyTemperatures(self, temperatures):stack, ret = [], [0] * len(temperatures)for i, num in enumerate(temperatures):while stack and temperatures[stack[-1]] < num:index = stack.pop()ret[index] = i - indexstack.append(i)return ret