普通栈：
class CQueue:
def __init__(self):
self.A, self.B = [], []
def appendTail(self, value: int) -> None:
self.A.append(value)
# 栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈再删除。
def deleteHead(self) -> int:
if self.B: return self.B.pop()
if not self.A: return -1
while self.A:
self.B.append(self.A.pop())
return self.B.pop()
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack1 = []
self.stack2 = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.stack1.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if len(self.stack2) == 0:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def peek(self) -> int:
"""
Get the front element.
"""
if len(self.stack2) == 0:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return len(self.stack2) == 0 and len(self.stack1) == 0
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.q = []
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.q.append(x)
q_length = len(self.q)
while q_length > 1:
self.q.append(self.q.pop(0)) #反转前n-1个元素，栈顶元素始终保留在队首
q_length -= 1
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.q.pop(0)
def top(self) -> int:
"""
Get the top element.
"""
return self.q[0]
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return not bool(self.q)
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
class Solution:
def isValid(self, s: str) -> bool:
if len(s) % 2 == 1: return False
pairs = {'(':')','[':']','{':'}'}
stack = list()
# stack中存左括号。 如果是左括号， 加入栈中； 如果是右括号， 判断栈顶元素的键的值是否等于当前元素
for c in s:
if c in pairs:
stack.append(c)
elif not stack or pairs[stack.pop()] != c:
return False
return not stack
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s: return 0
res = 0
# stack一边匹配消消乐， 一边入栈
# 这一步可以防止stack中匹配完为空时pop()报错
stack = [-1]
for i in range(len(s)):
if s[i] == "(":
stack.append(i)
else:
# 如果是右括号则出栈
stack.pop()
# 如果栈是空的话, 把右括号放进来
if not stack: stack.append(i)
# 当前全部数减去剩余无法配对的数（单身）即res
else: res = max(res, i - stack[-1])
return res
class Solution:
@lru_cache(None)
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return ['']
ans = []
for c in range(n):
for left in self.generateParenthesis(c):
for right in self.generateParenthesis(n-1-c):
ans.append('({}){}'.format(left, right))
return ans
class Solution:
def decodeString(self, s: str) -> str:
stack, res, multi = [], "", 0
for c in s:
if c == '[':
stack.append([multi, res])
res, multi = "", 0
elif c == ']':
cur_multi, cur_res = stack.pop()
res = cur_res + cur_multi * res
elif '0' <= c <= '9':
multi = multi * 10 + int(c)
else:
res += c
return res
'''
if 数字， then 将数字转换为整数，用于后续倍数计算
if 字符， 延长当前字符串
if 左括号，当前状态压入栈
if 右括号，弹出状态，组合字符串
'''
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
dict = {
"+": 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 = dict[token](num1, num2)
finally:
stack.append(num)
return stack[0]
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
i = j = 0
stack = []
for i in range(len(pushed)):
stack.append(pushed[i])
while stack and stack[-1] == popped[j]:
stack.pop()
j += 1
return not stack
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
stack1, stack2 = deque([]), deque([])
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.next
carry, p = 0, None
while stack1 or stack2 or carry:
num1 = stack1.pop() if stack1 else 0
num2 = stack2.pop() if stack2 else 0
ans = num1 + num2 + carry
carry = ans // 10
ans %= 10
# 递归思想
p = ListNode(ans, p)
return p
单调栈：
# Python3 辅助栈模拟
class SortedStack:
def __init__(self):
self.stack = list()
def push(self, val: int) -> None:
t = list()
while self.stack and self.stack[-1] < val:
t.append(self.stack.pop())
self.stack.append(val)
while t:
self.stack.append(t.pop())
def pop(self) -> None:
if not self.isEmpty():
self.stack.pop()
def peek(self) -> int:
if self.isEmpty():
return -1
return self.stack[-1]
def isEmpty(self) -> bool:
return len(self.stack) == 0
# Python3 堆模拟
# Your SortedStack object will be instantiated and called as such:
# obj = SortedStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.peek()
# param_4 = obj.isEmpty()
import heapq
class SortedStack:
def __init__(self):
self.stack = list()
heapq.heapify(self.stack)
def push(self, val: int) -> None:
heapq.heappush(self.stack,val)
def pop(self) -> None:
if not self.isEmpty():
ref = heapq.heappop(self.stack)
return ref
def peek(self) -> int:
if self.isEmpty():
return -1
ref = heapq.heappop(self.stack)
heapq.heappush(self.stack,ref)
return ref
def isEmpty(self) -> bool:
return len(self.stack) == 0
# Your SortedStack object will be instantiated and called as such:
# obj = SortedStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.peek()
# param_4 = obj.isEmpty()
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [math.inf]
def push(self, x: int) -> None:
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]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack, ans = [], [0] * len(temperatures)
# 1.若栈为空或当日温度小于栈顶温度，则直接入栈
# 2.若当日温度大于栈顶温度，说明栈顶元素升温日找到，将栈顶元素出栈，计算其与当日相差的天数
for day, tmp in enumerate(temperatures):
while stack and tmp > stack[-1][0]:
stack_tmp, stack_day = stack.pop()
ans[stack_day] = day - stack_day
stack.append((tmp, day))
return ans
剑指 Offer II 039. 直方图最大矩形面积
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = [-1]
heights.append(0)
n, ans = len(heights), 0
for i in range(n):
# 单调递增栈
while stack and heights[i] < heights[stack[-1]]:
p = stack.pop()
l, r = stack[-1], i
# 计算以栈顶元素勾勒出的最大面积
ans = max(ans, heights[p] * (r - l - 1))
stack.append(i)
return ans
class Solution:标签：return,int,self,pop,单调,stack,def From： https://blog.51cto.com/u_15905340/5919329
def maximalRectangle(self, matrix: List[List[str]]) -> int:
res_nums = [0]*len(matrix[0])
max_s = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if int(matrix[i][j]) == 0:
res_nums[j] = 0
res_nums[j] += int(matrix[i][j])
max_s = max(max_s, self.get_max_s(res_nums) ) # 求出当前形成柱形的面积，与之前比较取最大的面积
return max_s
def get_max_s(self, nums: list[int]): # 求柱形最大的面积，利用上题思路
nums.append(-1)
stack_index = []
res = 0
for i in range(len(nums)):
while stack_index != [] and nums[i] < nums[stack_index[-1]]:
h_index = stack_index.pop()
left = -1 if stack_index == [] else stack_index[-1]
res = max(res, (i - left -1)*nums[h_index])
stack_index.append(i)
return res