雨尽随笔

2025-08-22创建

写在最前

我不是写代码的高手，我甚至常常一行写完就怀疑自己。这里的内容不是自得自满，而是我记录自己跌跌撞撞留下的痕迹。若你看见这些代码觉得可笑，请你原谅我的笨拙，再顺手告诉我哪里错了，我会心怀感激。

155:最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

题解

class MinStack:
            def __init__(self):
                self.stack=[]
                self.min = [2**31]
            def push(self, val: int) -> None:
                self.stack.append(val)
                self.min.append(min(val,self.min[-1]))
            def pop(self) -> None:
                self.stack.pop()
                self.min.pop()
            def top(self) -> int:
                top=self.stack[-1]
                return top
        
            def getMin(self) -> int:
                return self.min[-1]

20:有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

题解

class Solution:
            def isValid(self, s: str) -> bool:
                list=[]
                for str in s:
                    list.append(str)
                def jud(a,b):
                    if a=='('and b==')':
                        return True
                    elif a=='['and b==']':
                        return True
                    elif a=='{' and b== '}':
                        return True
                    else:return False
                def syn(list):
                    if len(list)==0:
                        return True
                    elif len(list)%2 !=0:
                        return False
                    else: 
                        i=0
                        while i<=len(list)/2:
                            if list[i] in ['[','(','{']:
                                i+=1
                                continue
                            elif list[i] in [')',']','}']:
                                if jud(list[i-1],list[i]) and i!=0:
                                    list.pop(i)
                                    list.pop(i-1)
                                    return syn(list)
                                else:
                                    return False
                        return False
                return syn(list)

169：多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

class Solution:
            def majorityElement(self, nums: List[int]) -> int:
                n = len(nums)
                result = 0
                for i in set(nums):
                    coun = nums.count(i)
                    if coun >n/2:
                        result = i
                        break
                return result

239：滑动窗口最大值——单调队列

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：
解释：
滑动窗口的位置          最大值

[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：1

我自己的最初的解法是最原始的暴力解法，最后不出意外的报了 TimeOutError。参考了 Krahets 的题解，自己实现了 单调队列 来重新解。 

from typing import List
import collections

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        dq = collections.deque()  # 存放“值”的单调递减队列
        n = len(nums)
        for i, j in zip(range(1 - k, n - k + 1), range(n)):
            # 如果队首等于滑出窗口的元素，则从左侧弹出（完成“滑动”）
            if i >= 0 and dq and dq[0] == nums[i]:
                dq.popleft()
            # 保持队列单调：把所有比新元素小的从右侧弹出
            while dq and dq[-1] < nums[j]:
                dq.pop()
            dq.append(nums[j])
            res.append(dq[0])  # 队首即当前窗口最大值
        return res[k - 1:]

虽然最后成功通过，但只是狗尾续貂罢了，很佩服提出这个算法的大神。

104：二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

img

输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：

输入：root = [1,null,2]
输出：2

这个题的难度是简单，但这是我第一次接触树这个数据结构。思来想去，我的思路是使用 DFS（深度优先搜索）方法，获得所有叶子节点的深度，最后再获得最大值。

from typing import Optional, List

class Solution:
    class TreeNode:
        def __init__(self, val: int = 0, left: 'Solution.TreeNode' = None, right: 'Solution.TreeNode' = None):
            self.val = val
            self.left = left
            self.right = right

    def maxDepth(self, root: Optional['Solution.TreeNode']) -> int:
        res: List[int] = []  # 记录所有叶子节点的深度

        def dfs(node: Optional['Solution.TreeNode'], depth: int = 1) -> None:
            if not node:  # 空节点
                return
            if not node.left and not node.right:  # 叶子节点
                res.append(depth)
                return
            if node.left:
                dfs(node.left, depth + 1)
            if node.right:
                dfs(node.right, depth + 1)

        if not root:
            return 0  # 空树深度为 0
        dfs(root, 1)
        return max(res) if res else 0