【Leetcode-20】
一、题目：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
二、代码：
class Solution: def isValid(self, s: str) -> bool: look_up = {')': '(', '}': '{', ']': '['} stack = [] for item in s: if item in look_up.values(): stack.append(item) else: if stack and stack[-1] == look_up[item]: stack.pop() else: return False if len(stack) == 0: return True else: return False
一、题目：最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
二、代码：
def longestValidParentheses(self, s: str) -> int: if len(s) == 0: return 0 stack = [] matched = [] for i, item in enumerate(s): if len(stack) > 0 and stack[-1][0] == '(' and item == ')': top_index = stack.pop() matched.append([top_index[1], i]) else: stack.append((item, i)) if len(matched) == 0: return 0 matched = sorted(matched, key=lambda x: x[0]) p = matched[0] max_len = 0 for item in matched: if item[0] -1 <= p[1]: p = [p[0], max(p[1], item[1])] else: max_len = max(max_len, p[1]-p[0]+1) p = item max_len = max(max_len, p[1]-p[0]+1) return max_len
【Leetcode-42】
一、题目：接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
二、代码：
def trap(self, height: List[int]) -> int: """ 对每个柱子位置，计算左右最大值中最小的一个min_val,如果min_val>height[i]则存水量为min_val-height[i] """ right_max = [0] * len(height) p = 0 for i in reversed(range(len(height)-1)): p = max(p, height[i+1]) right_max[i] = p left_max = 0 res = 0 for i in range(1, len(height)): left_max = max(left_max, height[i-1]) min_val = min(left_max, right_max[i]) if min_val > height[i]: res += (min_val - height[i]) return res
【Leetcode-84】
一、题目：柱状图中的最大矩形
二、代码：
def largestRectangleArea(self, heights: List[int]) -> int: """ 从点往外扩展，计算第i个柱子能扩展出的最大宽，高度最高为h[i]，面积为宽*h[i] 单调递增栈，若后面高度有<h[i]的，则右边界可确定，单调栈中i的前一个元素为左边界 遍历完栈中可能有数据，即有的位置未计算出扩展的高度，那么元素尾部加-1可将全部元素弹出栈，头部或者栈底加-1可避免栈为空的判断 """ heights = heights + [0] stack = [-1] # 下标 max_area = 0 for i, item in enumerate(heights): while item < heights[stack[-1]]: height = heights[stack.pop()] width = i - stack[-1] - 1 # 此时的stack[-1]为左边界 max_area = max(max_area, height*width) stack.append(i) return max_area
【Leetcode-85】
一、题目：最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
二、代码：
def maximalRectangle(self, matrix: List[List[str]]) -> int: """ 对每一层计算柱子高度，有了柱子计算以柱子高为输入的最大矩形问题 """ def largest_area(heights): max_area = 0 heights = heights + [-1] stack = [-1] for i, item in enumerate(heights): while item < heights[stack[-1]]: height = heights[stack.pop()] width = i - stack[-1] - 1 max_area = max(max_area, height*width) stack.append(i) return max_area if len(matrix) == 0 or len(matrix[0]) == 0: return 0 # 对每一层计算柱子 final_area = 0 heights = [0] * len(matrix[0]) # 柱子有这么多列 for i, row in enumerate(matrix): # 对每一行 # 第i层为基座的柱子高度 for j, col in enumerate(row): if col == '1': heights[j] += 1 else: heights[j] = 0 area = largest_area(heights) final_area = max(final_area, area) return final_area
【Leetcode-155】
一、题目：最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
二、代码：
class MinStack: def __init__(self): """ initialize your data structure here. """ self.stack = [] self.min_stack = [] def push(self, val: int) -> None: if len(self.stack) == 0 or val < self.min_stack[-1]: self.min_stack.append(val) else: self.min_stack.append(self.min_stack[-1]) self.stack.append(val) def pop(self) -> None: self.min_stack.pop() self.stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1]
【Leetcode-224】
一、题目：基本计算器
给你一个字符串表达式 s （只包括+=()和空格），请你实现一个基本计算器来计算并返回它的值。
二、代码：
def calculate(self, s: str) -> int: """ 记录上一个操作符 遇到'(',前面的总和与现在的操作符进栈，方便与后面连接,num=0,res=0 遇到')',计算现在的总和，出栈结果与现在连接 遇到数字,更新数字 遇到操作符,根据前一个操作符更新总和 遇到空格，跳过 """ stack = [] s = list(s) + ['+'] num = res = 0 last_op = '+' for item in s: if '0' <= item <= '9': num = num * 10 + int(item) elif item == '(': stack.append([res, last_op]) num = res = 0 elif item == ')': flag = 1 if last_op == '+' else -1 res = res + flag * num # 更当前项的res,括号内的 last_item = stack.pop() flag = 1 if last_item[1] == '+' else -1 res = last_item[0] + flag * res # 更多项的res,括号内和括号前面的 num = 0 elif item in ['+', '-']: flag = 1 if last_op == '+' else -1 res = res + flag * num last_op = item num = 0 return res
【Leetcode-227】
一、题目：基本计算器2
给你一个字符串表达式 s （只包含+-*/和空格），请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
二、代码：
def calculate(self, s: str) -> int: """ 记录数字前面操作符 遇到操作符则数字进栈：前一个操作符为+-则直接进栈，*/则更新后再进栈，数字置0，记录操作符 遇到数字则更新数字 遇到空格跳过 """ res = [] num = 0 pre_op = '+' # 记录前一个操作符 s = list(s) + ['+'] for item in s: if '0' <= item <= '9': # 数字 num = num * 10 + int(item) elif item in ['+', '-', '*', '/']: # 遇到操作符需要处理数字，数字需要看前一个操作符 if pre_op == '+': res.append(num) elif pre_op == '-': res.append(-num) elif pre_op == '*': pre_num = res.pop() res.append(pre_num * num) else: pre_num = res.pop() res.append(int(pre_num / num)) # 先向下取整再加正负号 num = 0 pre_op = item return sum(res)
【Leetcode-321】
一、题目：拼接最大数
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
注意：可以只从一个数组选
二、代码：
def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]: """ 1.数组1选k1个元素，数组2选k-k1个，数组1和2选完需要各自最大，然后拼接最大 def concat(nums1, nums2): 不能如此选最大值，如[6,7]和[6]，可能选出667而不是676。原因为两个数组是无序的，有序才能这么选 if len(nums1) == 0: return trans(nums2) if len(nums2) == 0: return trans(nums1) res = '' n1 = len(nums1) n2 = len(nums2) p1, p2 = 0, 0 while p1 < n1 or p2 < n2: val1 = nums1[p1] if p1 < n1 else float('-inf') val2 = nums2[p2] if p2 < n2 else float('-inf') if val1 > val2: res += str(val1) p1 += 1 else: res += str(val2) p2 += 1 return int(res) """ def select_max(nums, k): stack = [] discard = len(nums) - k for item in nums: while stack and item > stack[-1] and discard > 0: stack.pop() discard -= 1 stack.append(item) return stack[:k] def trans(s): res = '' for item in s: res += str(item) return int(res) def merge(A, B): ans = [] while A or B: bigger = A if A > B else B # 按字典序比较 ans.append(bigger.pop(0)) return int(trans(ans)) max_res = 0 for k1 in range(len(nums1)+1): k2 = k - k1 if k2 < 0 or k2 > len(nums2): continue select1 = select_max(nums1, k1) select2 = select_max(nums2, k2) # num = concat(select1, select2) num = merge(select1, select2) max_res = max(max_res, num) return [int(t) for t in str(max_res)]
【Leetcode-394】
一、题目：字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
二、代码：
def decodeString(self, s: str) -> str: st = '' num = 0 stack = [] for char in s: if '0' <= char <= '9': # 数字 num = num * 10 + int(char) elif char == '[': stack.append((st, num)) st = '' num = 0 elif char == ']': last_st, last_num = stack.pop() st = last_st + st * last_num else: st = st + char return st
【Leetcode-316】
一、题目：去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
二、代码：
def removeDuplicateLetters(self, s: str) -> str: """ 1.第i+1位字典序小则剔除前面的可以使得结果更小 2.重复的才考虑剔除，因此需要预先统计哪些是重复的，重复多少次，当剔除到就剩一次就不能再剔除 3.重复字符不进栈，直接删除 4.用set维持栈中元素，便于查找某元素是否在栈中（判断是否是重复字符） """ char_cnt = {} for char in s: cnt = char_cnt.get(char, 0) char_cnt[char] = cnt + 1 stack = [] stack_set = set() for char in s: if char not in stack_set: # 重复字符不能进栈 while len(stack) > 0 and ord(stack[-1]) > ord(char) and char_cnt.get(stack[-1], 0) > 1: top = stack.pop() stack_set.remove(top) top_cnt = char_cnt.get(top, 0) char_cnt[top] = top_cnt - 1 stack.append(char) stack_set.add(char) else: cnt = char_cnt.get(char, 0) char_cnt[char] = cnt - 1 return ''.join(stack)
【Leetcode-402】
一、题目：移掉K位数字
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
二、代码：
def removeKdigits(self, num: str, k: int) -> str: """ 1.高位越大则数值越大，因此想获得最小的数字需要尽量把高位的较大的数字剔除 2.如1432219，剔除1位则剔除4，剔除两位则43，剔除3位则432，规律是第i+1位数字更小则第k-i位踢掉能使得最终数字更小 3.单调递增栈：新来的数字更小则把前面大的踢掉 4.剔除时需保证不能过量（只能踢k个） 5.可能踢完后数字长度>k，则截取len(num)-k个即可 """ n = len(num) remain = n - k stack = [] for item in num: while len(stack) > 0 and stack[-1]>item and k > 0: stack.pop() k -= 1 stack.append(item) res = stack[:remain] res = ''.join(res).lstrip('0') # 去除前导0 return res if res else '0'
【Leetcode-739】
一、题目：每日温度
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
二、代码：
def dailyTemperatures(self, T: List[int]) -> List[int]: """ 维护一个单调递减栈，记录下标i和温度，新来的元素j>栈顶元素则弹出栈顶，并记录弹出元素的结果为j-i,最终栈中剩余元素为观测不到更高温度，填入0 """ res = [0] * len(T) stack = [] for i, item in enumerate(T): while len(stack) > 0 and stack[-1][1] < item: pre = stack.pop() res[pre[0]] = i - pre[0] stack.append([i, item]) return res
【Leetcode-907】
一、题目：子数组的最小值之和
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7 。
1 <= arr.length <= 3 * pow(10, 4)
1 <= arr[i] <= 3 * pow(10, 4)
二、代码：
def sumSubarrayMins(self, arr: List[int]) -> int: """ 1.题目抽象为：计算经过i位置且最小值为arr[i]的子数组个数cnt[i]，求sum(cnt[i]*arr[i]) 2.求经过i位置且最小值为arr[i]的子数组：设i左边和右边第一个<arr[i]的位置分别为l和r,则cnt[i]=(i-l)*(r-i) 3.求l和r：单调递增栈，遇到<arr[i]的数则arr[i]的r确定，l为栈中arr[i]的底层一个位置 4.单调递增栈：加哨兵，避免开头和结尾的判断 """ arr = arr + [0] stack = [[-1, 0]] res = 0 m = pow(10, 9) + 7 for i, item in enumerate(arr): while item < stack[-1][1]: pos, _ = stack.pop() # 该位置的r确定 l = stack[-1][0] r = i this_cnt = (pos - l) * (r - pos) res += this_cnt*arr[pos] res %= m stack.append([i, item]) return res