Loading... # Stack、Queue ## 20.有效的括号 ### 题目描述 给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串 `s` ，判断字符串是否有效。 有效字符串需满足： 1. 左括号必须用相同类型的右括号闭合。 2. 左括号必须以正确的顺序闭合。 题目链接：https://leetcode-cn.com/problems/valid-parentheses/ ### 解法 1：暴力 ```python 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：使用辅助栈 ```python 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)==0 ``` ## 155.最小栈 ### 题目描述 设计一个支持 `push` ，`pop` ，`top` 操作，并能在常数时间内检索到最小元素的栈。 ```bash push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。 ``` 题目链接：https://leetcode-cn.com/problems/min-stack/ ### 解法 ```python 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：暴力求解 ```python 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：辅助栈 ```python 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/ ## TODO - https://leetcode-cn.com/problems/sliding-window-maximum - https://leetcode.com/problems/design-circular-deque - https://leetcode.com/problems/trapping-rain-water/ Last modification：January 27th, 2021 at 03:24 am © 允许规范转载