69、有效的括号
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
提示:
1 <= s.length <= 104
s
仅由括号'()[]{}'
组成
思路解答:
- 初始化一个空栈。
- 遍历字符串中的每个字符:
- 如果当前字符是左括号(‘(’,‘{’,‘[’),则将其推入栈中。
- 如果当前字符是右括号(‘)’,‘}’,‘]’),则检查栈顶元素:
- 如果栈为空,或者栈顶元素与当前字符不匹配,则返回 False。
- 如果栈顶元素与当前字符匹配,则弹出栈顶元素。
- 在遍历完成后,检查栈是否为空。如果栈为空,则说明所有括号都匹配,返回 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
, andgetMin
最多被调用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]
思路解答:
- 初始化一个空栈,用于存储当前的解码字符串。
- 遍历输入字符串中的每个字符:
- 如果当前字符不是右括号
]
,则将其推入栈中。 - 如果当前字符是右括号
]
,则从栈中弹出字符,直到遇到左括号[
,这些弹出的字符构成一个重复的字符串。- 继续弹出栈中的字符,直到栈顶是数字,将这个数字解析为重复次数
k
。 - 将重复次数
k
和构成的重复字符串相乘,得到新的重复字符串,并推入栈中。
- 继续弹出栈中的字符,直到栈顶是数字,将这个数字解析为重复次数
- 如果当前字符不是右括号
- 最终栈中剩下的字符即为解码后的字符串。
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
思路解答:
- 初始化一个空栈
stack
和一个长度与输入数组相同的结果数组answer
,初始值为0。 - 从左到右遍历温度数组
temperatures
:- 如果栈不为空且当前温度大于栈顶索引对应的温度:
- 弹出栈顶索引
top_index
,并计算当前索引与top_index
之间的天数差,即i - top_index
,这个天数差即为top_index
对应的下一个更高温度的天数。 - 将
answer[top_index]
更新为这个天数差。
- 弹出栈顶索引
- 将当前索引
i
推入栈中。
- 如果栈不为空且当前温度大于栈顶索引对应的温度:
- 返回结果数组
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
思路解答:
- 初始化一个空栈
stack
,并在输入数组的末尾添加一个高度为0的柱子,这样可以确保所有柱子都被处理到。 - 从左到右遍历柱子的高度数组:
- 如果栈为空或者当前柱子高度大于等于栈顶柱子的高度,将当前柱子的索引压入栈中。
- 如果当前柱子的高度小于栈顶柱子的高度,说明可以计算以栈顶柱子为高度的矩形的面积了:
- 弹出栈顶柱子的索引
top
。 - 计算以
top
为高度的矩形的宽度,即i - stack[-1] - 1
,其中i
是当前柱子的索引,stack[-1]
是栈中下一个柱子的索引。注:当前高度对应的最大面积 的 宽度 是 右边比他小的第一个 - 左边比它小的第一个 - 1 - 计算以
top
为高度的矩形的面积,即width * heights[top]
,其中width
是宽度,heights[top]
是栈顶柱子的高度。 - 更新最大面积。
- 弹出栈顶柱子的索引
- 返回最大面积。
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
标签:示例,python,题解,top,栈顶,pop,self,力扣,stack
From: https://blog.csdn.net/weixin_45554996/article/details/136662328