力扣hot100题解（python版69-73题）

69、有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

思路解答：

1. 初始化一个空栈。
2. 遍历字符串中的每个字符：
   • 如果当前字符是左括号（‘(’，‘{’，‘[’），则将其推入栈中。
   • 如果当前字符是右括号（‘)’，‘}’，‘]’），则检查栈顶元素：
     • 如果栈为空，或者栈顶元素与当前字符不匹配，则返回 False。
     • 如果栈顶元素与当前字符匹配，则弹出栈顶元素。
3. 在遍历完成后，检查栈是否为空。如果栈为空，则说明所有括号都匹配，返回 True；否则返回 False。

def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in mapping.values():
            stack.append(char)
        elif char in mapping:
            if not stack or mapping[char] != stack.pop():
                return False

    return not stack

70、最小栈

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

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 104 次

思路解答：

借用一个辅助栈 min_stack，用于存获取 stack 中最小值。

push() 方法： 每当push()新值进来时，如果 小于等于 min_stack 栈顶值，则一起 push() 到 min_stack，即更新了栈顶最小值。
pop() 方法： 判断将 pop() 出去的元素值是否是 min_stack 栈顶元素值（即最小值），如果是则将 min_stack 栈顶元素一起 pop()，这样可以保证 min_stack 栈顶元素始终是 stack 中的最小值。
getMin()方法： 返回 min_stack 栈顶即可。

class MinStack:

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

71、字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

提示：

• 1 <= s.length <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300]

思路解答：

1. 初始化一个空栈，用于存储当前的解码字符串。
2. 遍历输入字符串中的每个字符：
   • 如果当前字符不是右括号 ]，则将其推入栈中。
   • 如果当前字符是右括号 ]，则从栈中弹出字符，直到遇到左括号 [，这些弹出的字符构成一个重复的字符串。
     • 继续弹出栈中的字符，直到栈顶是数字，将这个数字解析为重复次数 k。
     • 将重复次数 k 和构成的重复字符串相乘，得到新的重复字符串，并推入栈中。
3. 最终栈中剩下的字符即为解码后的字符串。

def decodeString(s: str) -> str:
    stack = []
    current_str = ""
    current_num = 0

    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char.isalpha():
            current_str += char
        elif char == "[":
            stack.append(current_str)
            stack.append(current_num)
            current_str = ""
            current_num = 0
        elif char == "]":
            num = stack.pop()
            prev_str = stack.pop()
            current_str = prev_str + num * current_str

    return current_str

72、每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

思路解答：

1. 初始化一个空栈 stack 和一个长度与输入数组相同的结果数组 answer，初始值为0。
2. 从左到右遍历温度数组 temperatures：
   • 如果栈不为空且当前温度大于栈顶索引对应的温度：
     • 弹出栈顶索引 top_index，并计算当前索引与 top_index 之间的天数差，即 i - top_index，这个天数差即为 top_index 对应的下一个更高温度的天数。
     • 将 answer[top_index] 更新为这个天数差。
   • 将当前索引 i 推入栈中。
3. 返回结果数组 answer。

def dailyTemperatures(temperatures: list[int]) -> list[int]:

    n = len(temperatures)
    stack = []
    answer = [0] * n

    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            index = stack.pop()
            answer[top_index] = i - index

        stack.append(i)

    return answer

73、柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4]
输出： 4

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

思路解答：

1. 初始化一个空栈 stack，并在输入数组的末尾添加一个高度为0的柱子，这样可以确保所有柱子都被处理到。
2. 从左到右遍历柱子的高度数组：
   • 如果栈为空或者当前柱子高度大于等于栈顶柱子的高度，将当前柱子的索引压入栈中。
   • 如果当前柱子的高度小于栈顶柱子的高度，说明可以计算以栈顶柱子为高度的矩形的面积了：
     • 弹出栈顶柱子的索引 top。
     • 计算以 top 为高度的矩形的宽度，即 i - stack[-1] - 1，其中 i 是当前柱子的索引，stack[-1] 是栈中下一个柱子的索引。注：当前高度对应的最大面积 的 宽度 是 右边比他小的第一个 - 左边比它小的第一个 - 1
     • 计算以 top 为高度的矩形的面积，即 width * heights[top]，其中 width 是宽度，heights[top] 是栈顶柱子的高度。
     • 更新最大面积。
3. 返回最大面积。

def largestRectangleArea(heights: list[int]) -> int:
    heights.append(0)  # 添加高度为0的柱子
    n = len(heights)
    stack = []
    max_area = 0

    for i in range(n):
        while stack and heights[i] < heights[stack[-1]]:
            top = stack.pop()
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, width * heights[top])

        stack.append(i)

    return max_area