【Leetcode】top 100 栈
基础知识补充
1.栈是一种运算受限的线性表，仅允许在一端进行插入和删除操作；
2.可用列表实现，list.append(val) // list.pop()
题目
20 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
class Solution(object):def isValid(self, s):""":type s: str:rtype: bool"""stack = []for strr in s:if strr=='(' or strr=='[' or strr=='{': #左括号，入栈stack.append(strr)else: #右括号，判断是否匹配if not stack: return Falseelse:pre = stack.pop()if strr == ')' and pre != '(': return Falseelif strr == ']' and pre != '[': return Falseelif strr == '}' and pre != '{': return False return stack==[]写完初步代码发现实际上需要找的是右括号，然后判断右括号是否与对应左括号匹配，可以用 dict 构造成对关系：
class Solution(object):def isValid(self, s):""":type s: str:rtype: bool"""stack = []dict = {')':'(', ']':'[', '}':'{'}for strr in s:if not stack: stack.append(strr)else: if strr in dict: # 右括号，判断是否匹配if stack[-1]==dict[strr]: stack.pop()else: return Falseelse: # 左括号，入栈stack.append(strr)return not stack
155 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
正常维护一个栈完成入栈、出栈、取栈顶元素操作；
要求在常数时间内检索到最小元素，即用变量记录当前栈的最小值，与正常栈一起维护；
class MinStack(object):def __init__(self):self.stack = []self.min = 2**31def push(self, val):""":type val: int:rtype: None"""if not self.stack: self.stack.append([val, val])else:self.stack.append([val, min(val, self.stack[-1][1])])def pop(self):""":rtype: None"""if self.stack: self.stack.pop()def top(self):""":rtype: int"""if self.stack: nums = self.stack.pop()self.stack.append(nums)return nums[0]def getMin(self):""":rtype: int"""if self.stack: nums = self.stack.pop()self.stack.append(nums)return nums[1]
394 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
class Solution(object):def decodeString(self, s):""":type s: str:rtype: str"""stack = []for strr in s:if strr != ']': stack.append(strr)else:res, num, bit = [], 0, 1while stack:if stack[-1]=='[': breakval = stack.pop()res = list(val) + res # 注意先后顺序stack.pop()while stack:val = stack.pop()if val>='0' and val<='9':# num = val + num 也可以用字符串num = num+int(val)*bit bit = bit*10else: stack.append(val)breakstack.append(''.join(res*num))return ''.join(stack)
739 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
维护一个递减的单调栈，初始化间隔变量interval，若入栈元素大于栈顶元素，弹出栈顶元素并将其对应的输出坐标置为interval，然后 interval+1，继续循环至前一个大于等于当前元素的值；
问题出在怎么通过弹出的元素定位到其输出坐标？ 坐标表示，即栈内维护的是温度对应的下标，间隔 interval 就自然转化为入栈元素下标和出栈元素下标的差值；
class Solution(object):def dailyTemperatures(self, temperatures):""":type temperatures: List[int]:rtype: List[int]"""stack = []out = [0] * len(temperatures)# for i, tmp in enumerate(temperatures):# if not stack or temperatures[stack[-1]] >= tmp: # 栈空/前一温度大于等于当前温度# stack.append(i)# else: # 前一温度小于当前温度# while stack:# if temperatures[stack[-1]] >= tmp:break # 直至遇到前一温度大于等于当前温度# else:# idx = stack.pop()# out[idx] = i-idx# stack.append(i)# if/else 都要 append 简化一下：for i, tmp in enumerate(temperatures):while stack and temperatures[stack[-1]] < tmp:idx = stack.pop()out[idx] = i-idxstack.append(i)return out
84 柱状图中的最大矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
对于高度为 height[i] 的矩形，最大面积的宽为其左右第一个小于该高度的元素下标差-1，故将问题转换为给定高度为 height[i]，求其左右第一个小于该高度的元素下标差；
left[i] 为 height[i] 的左界下标，right[i] 为 height[i] 的右界下标；单调栈问题
class Solution(object):def largestRectangleArea(self, heights):""":type heights: List[int]:rtype: int"""n = len(heights)left, right = [-1]*n, [n]*nstack = []for i in range(n):while stack and heights[stack[-1]] >= heights[i]: # 找到val的左界stack.pop()if stack: left[i] = stack[-1]stack.append(i)print(left)stack = []for i in range(n-1, -1, -1): while stack and heights[stack[-1]] >= heights[i]: # 找到val的右界stack.pop()if stack: right[i] = stack[-1]stack.append(i)print(right)out = 0for i in range(n):ans = heights[i]*(right[i]-left[i]-1)out = max(ans, out)return out与 42接雨水 类似，待后续一起总结