数据结构-栈结构扩展应用

LeetCode 20 有效的括号

结论1：在任意⼀个位置上，左括号数量 右括号数量
结论2：在最后⼀个位置上，左括号数量 右括号数量
根据上述两个结论，程序中只需要记录左括号和右括号的数量即可。

⼀对括号可以等价为⼀个完整的事件。左括号可以看作事件的开始、右括号可以看 作事件的结束。⽽括号序列可以看作事件与事件之间的完全包含关系。
栈可以处理具有完全包含关系的问题。

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 != 0: return False
        stack = []
        dic = {')':'(',']':'[','}':'{'}
        for s_i in s:
            if stack and s_i in dic:
                if stack[-1] == dic[s_i]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(s_i)
        return len(stack) == 0 

LeetCode 1021 删除最外层的括号

左括号和右括号差值为0时，代表这⼀串括号序列是独⽴的，可以被单独分解出来。

class Solution:
    def removeOuterParentheses(self, s: str) -> str:
        count_num = 0
        ans = ''
        for s_i in s:
            if s_i == '(':
                if count_num  > 0:
                    # count_num += 1
                    ans += s_i
                 # 表示栈没有左括号，所以不能记录下来 
                count_num += 1
            else:
                if count_num > 1:
                    ans  += s_i
                count_num -= 1
        return ans 

LeetCode 1249 移除⽆效的括号

可以被匹配的括号都是有效的，⽽其他的括号都需要被删除。

class Solution:
    def minRemoveToMakeValid(self, s: str) -> str:
        stack = []
        s_list =  list(s)
        for i in range(len(s_list)):#栈需要存储的不是括号需要看括号的下标
            if s_list[i] == '(':
                stack.append(i)
            elif s_list[i] == ')':
                if stack and s_list[stack[-1]] == '(':
                    stack.pop()
                else:
                    stack.append(i)        
        while stack:
            s_list.pop(int(stack.pop())) 
        return ''.join(s_list)

LeetCode 145 ⼆叉树的后序遍历

递归做法⽐较简单，在这⾥介绍⼀下基于迭代的做法。 技巧是使⽤两个栈，⼀个数据栈，⼀个状态栈。将“遍历左⼦树”，“遍历右⼦ 树”和“访问根节点”三个步骤分别⽤状态码表⽰，枚举状态转移过程，使⽤有限 状态⾃动机（FSM, Finite State Machine）的模型来模拟递归过程。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        def postordef(root):
            if not root:
                return 
            postordef(root.left)
            postordef(root.right)
            tem.append(root.val)
            return 
        
        tem = []
        postordef(root)
        return tem

LeetCode 331 验证⼆叉树的前序序列化

思路1：每次拆掉⼀个“数字、#、#”的节点（即叶⼦结点），最后树上的全部节点 都会被拆光（即只剩⼀个“#”），能拆光的序列就是合法序列。

思路2：初始状态有⼀个坑。每多增加⼀个数字节点，会在占掉⼀个坑后，产⽣两个
坑，每多增加⼀个#，会减少⼀个坑。合法的⼆叉树前序遍历最后会刚好⽤完所有的 坑。

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        if len(preorder) == 0: return False 
        preorder = preorder.split(',')
        stack = [1]  # 根节点的可能性
        for data in preorder:
            if len(stack) == 0: return False
            stack[-1] -= 1 # 不管进来的元素是否是#， 都需要把之前的栈顶的节点的可能性-1
            if stack[-1] == 0: # 如果此时的栈顶元素的可能性为0 , 那么不可能再往下发展了，需要移除，同时向下一个栈顶去查看可能性
                stack.pop() 
            if data != '#': # 如果当前值不是 #, 则要消耗掉栈顶的一个可能性 （-1）， 同时产生两种可能性
                stack.append(2)
            # else:          #当前是#，则会占用一个可能性，但是不产生可能性
            #     stack[-1] -= 1
        return len(stack) == 0

LeetCode 227 基本计算器II

思路1：找到式⼦中优先级最低的运算符，然后递归分治运算两侧的⼦式即可。

思路2：使⽤操作数栈和操作符栈辅助计算，当操作符栈遇到更低优先级的操作符 时，需要将之前更⾼级别的操作符对应的结果计算出来。 对于有括号的情况，左括号相当于提⾼了内部全部运算符的优先级，当遇到右括号 的时候需要将匹配的括号间的内容全部计算出来。 可以通过加⼀个特殊操作符的处理技巧，来额外处理结尾的数字。

class Solution:
    def calculate(self, s: str) -> int:
        s = s.replace(' ','')
        stack = []
        op  = '+'
        num = 0
        for i, data in enumerate(s): # 节目效果，也是节目效果
            # 如果遍历到的data 是数字 35 
            if data.isdigit():
                num = num * 10 + int(data)
            if data  in '+-*/' or i == len(s) - 1: #i 用作最后一位元素的时候进行计算 
                if op == '+':
                    stack.append(num)
                elif op == '-':
                    stack.append(-num)
                elif op == '*':
                    stack[-1] = stack[-1] * num
                else: # 3/ 2 => 1 
                    stack[-1] = -(abs(stack[-1]) // num) if stack[-1] < 0 else stack[-1] // num
                num = 0
                op = data

        return sum(stack)

LeetCode 636 函数的独占时间

本质就是⼀道模拟题，画⼀个线段图能显著地辅助理解。任务开始时进栈，上⼀个 任务暂停执⾏；任务完成时出栈，恢复上⼀个任务的执行。

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        logs = [log.split(':') for log in logs]
        stack = []
        log_time = [0] * n  # A:0 , B:1 
        for log in logs: # log 结构是【任务名，开始或者结束，时间序列】
            if log[1] == "start":
                stack.append(log)
            else:
                time = int(log[2]) - int(stack.pop()[2]) + 1
                log_time[int(log[0])] += time
                if stack:
                    log_time[int(stack[-1][0])] -= time 
        
        return log_time

LeetCode 1124 表现良好的最⻓时间段

把表现“良好”记为+1，把表现“不好”记为-1，将原序列转化为正负1的序列，原 问题转化为求转化后序列的最⻓⼀段连续⼦序列，使得⼦序列的和⼤于0。 在这⾥引⼊“前缀和”的技巧。前缀和数组的第n项，是原数组前n项的和。 记原数组为 ，那么前缀和
。这样就可以将“区间和”转化 为“前缀和”之差来计算。前缀和可以视情况补⼀个前导0，表⽰前0项之和，即不 取任何元素的情况。 在本题中， 数组中的元素只有-1和1，因此前缀和prefix 的变化⼀定是连续的。我 们记录下前缀和中，每⼀个前缀和第⼀次出现的位置，它对应的位置⼀定是从该前 缀和出发的最优解。
我们以f(n) 表⽰以 结尾的序列的最⼤⻓度，pos(n) 表⽰前缀和 第⼀次出现的位 置。那么有

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        len_n = len(hours)
        score = [0] * len_n
        for i in range(len_n):
            score[i] = 1 if hours[i] > 8 else - 1
        # 前缀和
        presum = [0] * (len_n + 1) #[0, 0, 0, 0, 0]
        for i in range(1, len_n  + 1):
            presum[i] = presum[i - 1] + score[i - 1]

        stack = [] # 单调栈 
        for i in range(len_n + 1):
            if not stack or presum[i] < presum[stack[-1]]:  # 若栈里没有元素，要入栈，若有元素，则满足栈顶元素所对应的前缀和>  后续所遍历的前缀和的，就入栈  
                stack.append(i)
        j = len_n  # 将右序遍历的j 进行放到最后面
        ans = 0
        while j > ans:
            while stack and presum[j] > presum[stack[-1]]: # b
               ans = max(ans, j - stack.pop()) 
            j -= 1
        return ans