代码随想录算法训练营 Day 41
Published:
单调栈
一维数组中要找到一个元素的左边或者右边第一个比自己大或者小的元素的位置，就可以使用单调栈。单调栈中就只需要存放索引，可以直接用索引得到所指向的元素
Q1. LeetCode 739
要找到右侧（数组尾部方向）第一个比当前大的元素，那么就可以使用单调递增的单调栈
如果求一个元素右边第一个更大元素，单调栈就是递增的，如果求一个元素右边第一个更小元素，单调栈就是递减的。
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
answer = [0] * len(temperatures)
stack = [0]
for i in range(1, len(temperatures)):
if temperatures[i] <= temperatures[stack[-1]]:
stack.append(i)
else:
while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:
answer[stack[-1]] = i - stack[-1]
stack.pop()
stack.append(i)
return answer
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q2. LeetCode 496
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
res = [-1] * n
stack = [0]
for i in range(1, len(nums2)):
if nums2[i] <= nums2[stack[-1]]:
stack.append(i)
else:
while stack and nums2[i] > nums2[stack[-1]]:
if nums2[stack[-1]] in nums1:
index = nums1.index(nums2[stack[-1]])
res[index] = nums2[i]
stack.pop()
stack.append(i)
return res
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q3. LeetCode 503
对于循环数组，只需要遍历两次即可
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [-1] * n
stack = [0]
for i in range(n):
if nums[i] <= nums[stack[-1]]:
stack.append(i)
else:
while stack and nums[i] > nums[stack[-1]]:
res[stack[-1]] = nums[i]
stack.pop()
stack.append(i)
for i in range(n):
if not stack:
return res
while stack and nums[i] > nums[stack[-1]]:
res[stack[-1]] = nums[i]
stack.pop()
return res
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)