单调栈
顾名思义，首先是一个栈，然后在使用时遵循一定规律。一般是新元素入栈前，对比栈顶元素和新元素的关系，满足一定条件则不断弹出栈顶元素，做业务处理，然后才新元素入栈。
通常用于寻找下/前一个的更大/小元素，或者滑动窗口的最大/小值。
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 ans2. 接雨水
难度
- 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 ans3. 每日温度
难度
- 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 ans4. 股票价格跨度
难度
- 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 res5. 超级丑数
难度
- 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 s8. 分割数组为连续子序列
难度
- 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