2024.6.13刷题记录

目录

一、828. 模拟栈 - AcWing题库

1.使用列表实现-摸鱼法

2.使用数组实现

二、AcWing 3302. 表达式求值 - AcWing

三、829. 模拟队列 - AcWing题库

四、830. 单调栈 - AcWing题库

五、154. 滑动窗口 - AcWing题库

---

一、828. 模拟栈 - AcWing题库

1.使用列表实现-摸鱼法

# 使用列表实现
'''
push x – 向栈顶插入一个数 x；
pop – 从栈顶弹出一个数；
empty – 判断栈是否为空；
query – 查询栈顶元素。
'''
def push(stack, x):
    stack.append(x)
    
def pop(stack):
    stack.pop()
    
def empty(stack):
    return 'YES' if len(stack) == 0 else 'NO'
 
def query(stack):
    return stack[-1]
    
if __name__ == '__main__':
    m = int(input())
    stack = []
    for _ in range(m):
        oper = input().split()
        if oper[0] == 'push':
            push(stack, int(oper[1]))
        elif oper[0] == 'pop':
            pop(stack)
        elif oper[0] == 'empty':
            print(empty(stack))
        else:
            print(query(stack))

2.使用数组实现

多用数组实现。

# 使用数组实现
def init(N = 100010):
    global stack, top
    stack = [0] * N
    top = 0     # 栈顶指针
 
def push(x):
    global stack, top
    stack[top] = x
    top += 1
 
def pop():
    global stack, top
    top -= 1
    
def empty():
    global stack, top
    return 'YES' if top <= 0 else 'NO'   # 栈顶指针同时代表有多少个元素
 
def query():
    global stack, top
    return stack[top - 1]
    
 
m = int(input())
init()
for _ in range(m):
    oper = input().split()
    if oper[0] == 'push':
        push(int(oper[1]))
    elif oper[0] == 'pop':
        pop()
    elif oper[0] == 'empty':
        print(empty())
    else:
        print(query())

二、AcWing 3302. 表达式求值 - AcWing

不会，思路来自题解（AcWing 3302. 表达式求值：多图讲解运算符优先级+详细代码注释 - AcWing），代码来自题解（AcWing 3302. 表达式求值 - AcWing）。

dic = {'(': 0, '+': 1, "-": 1, '*': 2, '/': 2}  # 优先级
op = []
num = []
 
def new_eval():
    # 计算函数
    b = num.pop()   # 注意弹出顺序
    a = num.pop()
    c = op.pop()
    if c == '+':
        x = a + b
    elif c == '-':
        x = a - b
    elif c == '*':
        x = a * b
    else:
        x = int(a / b)   # 向0取整
    num.append(x)   # 压回栈
    
s = input()
n = len(s)
i = 0
while i < n:
    c = s[i]
    if c.isdigit():     # 该函数检查字符是否为数字 
        x = 0
        while i < n and s[i].isdigit():
            x = x * 10 + int(s[i])
            i += 1
        # 循环结束时为运算符，退回一次进入下一次判断
        i -= 1  # 重要
        num.append(x)
    elif c == '(':
        # 左括号直接入栈
        op.append('(')
    elif c == ')':
        # 弹出进行运算，直到遇见'('
        while op[-1] != '(':
            new_eval()
        op.pop()  # 左括号不要
    else:
        # 运算符
        while len(op) and dic[op[-1]] >= dic[c]:
            # 当运算符栈顶优先级大于等于遇到的运算符
            # 弹出运算
            # 当栈顶为左括号时直接进
            new_eval()
        # 入栈
        op.append(c)
    i += 1
    
# 栈内剩余元素运算
while len(op):
    new_eval()
print(num[-1])  # 最后的栈顶即为运算结果

三、829. 模拟队列 - AcWing题库

def init(N = 100010):
    global queue, front, rear
    queue = [0] * N
    front = -1
    rear = -1
 
def push(x):
    global queue, rear
    rear += 1
    queue[rear] = x
    
def pop():
    global front
    front += 1
 
def empty():
    global front, rear
    return "YES" if front >= rear else "NO"
    
def query():
    global queue, front, rear
    return queue[front + 1]
    
m = int(input())
init()
for _ in range(m):
    oper = input().split()
    if oper[0] == "push":
        push(int(int(oper[1])))
    elif oper[0] == "pop":
        pop()
    elif oper[0] == "empty":
        print(empty())
    else:
        print(query())

四、830. 单调栈 - AcWing题库

n = int(input())
nums = list(map(int, input().split()))
st = []     # 维护左边的单调递增栈
# ans = [-1] * n
for i, x in enumerate(nums):
    ans = -1    # 节省储存空间
    while st and st[-1] >= x:   # 维护单调递增
        st.pop()
    # if st: ans[i] = st[-1]
    if st: ans = st[-1]
    print(ans, end = ' ')
    st.append(x)
 
# # 输出
# for x in ans: print(x, end = ' ')

五、154. 滑动窗口 - AcWing题库

思路来自题解（AcWing 154. 滑动窗口---海绵宝宝来喽 - AcWing）

当时没有想到怎么保证队内全都是窗口内的元素，答案：“当队头元素在窗口的左边的时候，弹出队头”，虽然不能保证队内一直没有窗口外的元素，但是能保证使用到的队内元素（队头）全是窗口内元素。当时是有想到这个方法的，但是以为不行，一下没转过来弯。

代码来自题解（AcWing 154. 滑动窗口 - AcWing）

队列储存索引而不是元素，通过储存索引使我们能够快速判断元素是否出窗口。

# 先进先出
# 单调队列（本质上是双端队列）
N = 1000010
queue = [0] * N   # 储存下标
front, rear = 0, -1
n, k = map(int, input().split())
nums = list(map(int, input().split()))
 
# 求最小值，单调递增队列
for i, x in enumerate(nums):
    # 弹出队头越界值
    while front <= rear and i - k >= queue[front]:
        front += 1
    # 弹出末尾大于x的值，注意这里是值比较
    while front <= rear and nums[queue[rear]] > x:
        rear -= 1
    # 将rear放入末尾
    rear += 1
    queue[rear] = i     # 注意这里是下标而不是值
    # 输出，注意这里是k - 1，因为第一个窗口也要输出
    if i >= k - 1:
        print(nums[queue[front]], end = ' ')
print()
 
front, rear = 0, -1     # 初始化    
# 求最大值，单调递减队列
for i, x in enumerate(nums):
    # 队头弹出
    while front <= rear and i - k + 1 > queue[front]:
        front += 1
    # 队尾弹出，弹出操作均需要判断是否为空
    while front <= rear and nums[queue[rear]] < x:
        rear -= 1
    # 加入下标
    rear += 1
    queue[rear] = i
    # 输出
    if i >= k - 1:
        print(nums[queue[front]], end = ' ')

完

感谢你看到这里！一起加油吧！