Stack、Queue
20.有效的括号
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
题目链接：https://leetcode-cn.com/problems/valid-parentheses/
解法 1：暴力
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
while "{}" in s or '[]' in s or '()' in s:
s = s.replace('{}','').replace('[]','').replace('()','')
return s ==''使用replace函数，需要注意一下 while 循环终止条件。
解法 2：使用辅助栈
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for i in s:
if i =='{':
stack.append('}')
elif i == '(':
stack.append(')')
elif i == '[':
stack.append(']')
elif len(stack) != 0 and i == stack[-1]:
stack.pop()
else:
return False
return len(stack)==0155.最小栈
题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。题目链接：https://leetcode-cn.com/problems/min-stack/
解法
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min_stack = []
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self):
"""
:rtype: None
"""
if self.stack:
x = self.stack.pop()
if x == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
"""
:rtype: int
"""
if not self.stack: return -1
return self.stack[-1]
def getMin(self):
"""
:rtype: int
"""
if self.min_stack:
return self.min_stack[-1]
return 0
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()题目要求在常数时间内获得栈中的最小值，因此不能在 getMin() 的时候再去计算最小值，所以可以维护两个栈，用来存放最小值，这也是一种常见的做法。
84.柱状图中最大的矩形
题目描述
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
题目链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
解法 1：暴力求解
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
res = 0
for i in range(len(heights)):
# 当前高度
cur_height = heights[i]
# 取当前高度时的左边界
left = i
while left > 0 and heights[left-1]>=cur_height:
left-=1
# 取当前高度时的右边界
right = i
while right<len(heights)-1 and heights[right+1]>=cur_height:
right+=1
#更新最大值
res = max(cur_height*(right-left+1),res)
return res这种可以求解，时间复杂度为$O(n^2)$，实际提交的时候超时了。
解法 2：辅助栈
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
res = 0
# 加入哨兵结点
heights = [0] + heights + [0]
stack = [0]
# 第一个是哨兵结点，所以从1开始遍历
for i in range(1,len(heights)):
# 当高度小于栈顶时，说明找到了右边界
while heights[i] < heights[stack[-1]]:
cur_height = heights[stack.pop()]
cur_width = i-stack[-1] -1
res = max(cur_height*cur_width,res)
stack.append(i)
return res这里参考了 LeetCode 的题解：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/
