3.1 单调栈
1509字约5分钟
LeetcodePython
2024-12-04
他向远方望去,无法看到高山背后的矮山,只能看到一座座更高的山峰。
推荐先做做 8.【题单】常用数据结构 中的「枚举右,维护左」再来刷本题单。
及时去掉无用数据,保证栈中数据有序
从右往左写法,每次循环必定计算一个答案
class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: n = len(temperatures) ans = [0] * n st = [] for i in range(n - 1, -1, -1): while st and temperatures[i] >= temperatures[st[-1]]: st.pop() if st: ans[i] = st[-1] - i st.append(i) return ans
时间复杂度:O(n),其中 n 为 temperatures 的长度。虽然我们写了个二重循环,但站在每个元素的视角看,这个元素在二重循环中最多入栈出栈各一次,因此循环次数之和是 O(n),所以时间复杂度是 O(n)。
空间复杂度:O(min(n,U)),其中 U=max(temperatures)−min(temperatures)+1。返回值不计入,仅考虑栈的最大空间消耗
从左往右写法,栈里存储的都是没有找到答案的数,一但找到一个比他们大的,就弹出栈内小的元素,然后更新答案。可能执行多次循环才能找到答案,并一个计算出多个答案
class Solution: def dailyTemperatures(self, temperatures: List[int]) -> List[int]: n = len(temperatures) ans = [0] * n st = [] for i in range(n): while st and temperatures[i] > temperatures[st[-1]]: j = st.pop() ans[j] = i - j st.append(i) return ans
时间复杂度:O(n)
空间复杂度:O(n)。注意这种写法栈中可以有重复元素。
class Solution: def finalPrices(self, prices: List[int]) -> List[int]: res = prices st = [] for i, price in enumerate(prices): while st and price <= prices[st[-1]]: j = st.pop() res[j] = prices[j] - price st.append(i) return res
时间复杂度:O(n)
空间复杂度:O(n)
先计算nums2中各个元素的下一个更大元素,再遍历 nums1 写回答案的做法。但是当nums1只有一个元素,nums2有10^4个元素,这时间复杂度就高得离谱了
class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: dic = {} st = [] res = [] # 先计算nums2中各个元素的下一个更大元素 for i in range(len(nums2)): while st and nums2[i] > nums2[st[-1]]: j = st.pop() dic[nums2[j]] = nums2[i] st.append(i) # 再遍历 nums1 写回答案 for i, num in enumerate(nums1): if num in dic: res.append(dic[num]) else: res.append(-1) return res
时间复杂度:O(n + m),其中 n 是 nums1 的长度,m 是 nums2 的长度。
空间复杂度:O(n + m)
优化:可以只把 nums1 的元素入栈,在 nums2 中查找 nums1 元素后的第一个最大值
class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: dic = {num: i for i, num in enumerate(nums1)} st = [] res = [-1] * len(nums1) for num in nums2: while st and num > st[-1]: j = st.pop() res[dic[j]] = num if num in dic: st.append(num) # 只把在 nums1 中的元素入栈 return res
时间复杂度:O(n + m),其中 n 是 nums1 的长度,m 是 nums2 的长度。
空间复杂度:O(n + m)
简单粗暴直接把单调栈用两次
class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: n = len(nums) res = [-1] * n st = [] for i, num in enumerate(nums): while st and num > nums[st[-1]]: j = st.pop() res[j] = num st.append(i) for i, num in enumerate(nums): while st and num > nums[st[-1]]: j = st.pop() res[j] = num st.append(i) return res
时间复杂度:O(n),其中 n 是 nums 的长度。
空间复杂度:O(n)
优化:使用 % 来合并两个循环
class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: n = len(nums) res = [-1] * n st = [] for i in range(2 * n): while st and nums[i % n] > nums[st[-1]]: j = st.pop() res[j] = nums[i % n] st.append(i % n) return res
时间复杂度:O(n + m),其中 n 是 nums1 的长度,m 是 nums2 的长度。
空间复杂度:O(n + m)
因为链表没法确定res的小标,可以在栈内存储一个元组,同时记录下标和值;元组内的元素不可修改,但是整体可以被 pop 弹出
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]: res = [] st = [] # (索引, 值) (0, 2) cur = head while cur: while st and cur.val > st[-1][1]: j = st.pop()[0] res[j] = cur.val st.append((len(res), cur.val)) res.append(0) cur = cur.next return res
时间复杂度:O(n),其中 n 是 nums 的长度。
空间复杂度:O(n)
class Solution: def maxWidthRamp(self, nums: List[int]) -> int: # nums = [6,0,8,2,1,5] n = len(nums) st = [] res = 0 # 从左往右构造一个单调递减栈 [0, 1] 对应 [6, 0] # 如果 8 也加入栈,能在后面找到比 8 大的元素,一定比 6 和 0 大,所以构造单调递减栈 for i, num in enumerate(nums): while not st or num < nums[st[-1]]: st.append(i) # 从右往左找到第一个比栈顶大的,作为预备宽度最大值 for j in range(n - 1, -1, -1): while st and nums[j] >= nums[st[-1]]: res = max(res, j - st.pop()) return res
时间复杂度:O(n),其中 n 是 nums 的长度。
空间复杂度:O(n)
看不懂
时间复杂度:O(n)
空间复杂度:O(n)
class StockSpanner: def __init__(self): self.st = [(-1, inf)] self.i = -1 def next(self, price: int) -> int: self.i += 1 while self.st[-1][1] <= price: self.st.pop() self.st.append((self.i, price)) return self.i - self.st[-2][0] # Your StockSpanner object will be instantiated and called as such: # obj = StockSpanner() # param_1 = obj.next(price)
时间复杂度:均摊 O(1)。因为每个元素至多入栈出栈各一次。
空间复杂度:O(min(q,U))。其中 q 为 next 的调用次数,U 为 price 的范围。注意栈中没有重复元素,在 price 值域很小的情况下,空间复杂度主要取决于 price 的值域范围。