单调栈
顾名思义，首先是一个栈，然后在使用时遵循一定规律。一般是新元素入栈前，对比栈顶元素和新元素的关系，满足一定条件则不断弹出栈顶元素，做业务处理，然后才新元素入栈。
通常用于寻找下/前一个的更大/小元素，或者滑动窗口的最大/小值。
1. 下一个更大元素 II
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
代码
class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: stack = [] # 保存下标和元素 n = len(nums) ans = [-1 for i in range(n)] for i in range(2 * n): j = i % n while stack and stack[-1][1] < nums[j]: originPos, _ = stack.pop() ans[originPos] = nums[j] stack.append([j, nums[j]]) return ans
2. 接雨水
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
只有在遇到的下一个元素大于当前元素时，才有可能产生一个可以存水的图形，所以使用单调栈。
当左侧元素小于自身，右侧元素大于自身时，对存水量的贡献暂时为负。这部分需要好好体会。
代码
class Solution: def trap(self, height: List[int]) -> int: stack = [] ans = 0 n = len(height) for index in range(n): h = height[index] while stack and height[stack[-1]] <= h: rightEdge = stack.pop() if stack: ans += (min(height[stack[-1]], h) - height[rightEdge]) * (index - stack[-1] - 1) stack.append(index) return ans
3. 每日温度
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
比较明显的可以用单调栈。
代码
class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: n = len(temperatures) ans = [0 for i in range(n)] stack = [] # 存储下标 for index in range(n): while stack and temperatures[stack[-1]] < temperatures[index]: preDay = stack.pop() ans[preDay] = index - preDay stack.append(index) return ans
4. 股票价格跨度
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
要注意到当前元素的跨度跟之前元素的跨度之间的关系。
如果当前元素大于前一个元素，那么累加前一个元素的跨度，然后把前一个元素弹出。
代码
class StockSpanner: __stack: List[List[int]] def __init__(self): self.__stack = [] def next(self, price: int) -> int: res = 1 while self.__stack and self.__stack[-1][1] <= price: res += self.__stack.pop()[0] self.__stack.append([res, price]) return res
5. 超级丑数
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
之前在写丑数时就考虑到更多质因数的情况，代码可以直接用了。生成新的丑数的方法是一样的，最小元素逐个乘以十质因数即可。就算再来超超超超超级丑数，也是一样做。
代码
class Solution: def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int: hp = [1] cnt = 0 records = set() while True: cur = heappop(hp) cnt += 1 if cnt == n: return cur for factor in primes: num = cur * factor if num not in records: records.add(num) heappush(hp, num)
6. 有序矩阵中第 K 小的元素
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
会错意了，以为要时间复杂度小于 n 的平方。
直接维护一个固定大小的堆就好了。因为要的是第k小的元素，当大小大于k时，我们需要弹出最大元素，所以存储负值。那么最后堆顶元素的负值就是所求。
代码
class Solution: def kthSmallest(self, matrix: List[List[int]], k: int) -> int: hp = [] n = len(matrix) for i in range(n): for j in range(n): heappush(hp, -matrix[i][j]) if len(hp) > k: heappop(hp) return -hp[0]
7. 根据字符出现频率排序
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
字符种类有限，先用定长数组统计字符频率，然后用两个元素的数组存储频率（负值）和字符（ascii）的对应关系，并插入堆中。最后逐个出堆并构造字符串。
代码
class Solution: def frequencySort(self, s: str) -> str: freq = [0 for i in range(123)] hp = [] for ch in s: freq[ord(ch)] += 1 for i in range(48, 123): if freq[i] != 0: heappush(hp, [-freq[i], i]) s = "" while hp: num, ch = heappop(hp) s += chr(ch) * (-num) return s
8. 分割数组为连续子序列
难度
- Easy
- Medium
- Hard
完成情况
- 独立完成
- 参考思路
- 参考答案
思路
当遇到一个元素 num 时，我们优先考虑是否存在一个以 num - 1 结尾的序列，如果存在，应当将其加入到该序列末尾，且该序列最好是同类序列中最短的一个；否则，应当新建一个仅包含 num 的序列。最后，根据每个序列的长度，判断能否成功分割。如此一来，我们需要保存每个序列的末尾元素和长度信息（每次获取最小值）。可以使用一个字典，键为末尾元素，值为序列长度。
代码
class Solution: def isPossible(self, nums: List[int]) -> bool: dic = defaultdict(list) for num in nums: if dic[num - 1]: len = heappop(dic[num - 1]) heappush(dic[num], len + 1) else: heappush(dic[num], 1) keys = dic.keys() for key in keys: if dic[key] and dic[key][0] < 3: return False return True
Comments NOTHING