class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
ans = [0] * n
# 单调增的栈
stack = []
for i in range(n):
# 如果遍历的 temperatures[i] 比栈顶元素小，则先入栈
while len(stack) > 0 and temperatures[i] > temperatures[stack[-1]]:
ans[stack[-1]] = i - stack[-1]
stack.pop()
stack.append(i)
return ans
496.下一个更大元素 I
方法一:
通过单调栈列出 nums2 每个元素更大元素的值
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums2)
ans2 = [0] * n
stack = []
for i in range(len(nums2)):
while len(stack) > 0 and nums2[i] > nums2[stack[-1]]:
ans2[stack[-1]] = i
stack.pop()
stack.append(i)
ans1 = [-1] * len(nums1)
for i, num in enumerate(nums1):
ans2_index = nums2.index(num)
if ans2[ans2_index] == 0:
ans1[i] = -1
else:
ans1[i] = nums2[ans2[ans2_index]]
return ans1
简洁版
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
res = [-1] * n
stack = []
for i in range(len(nums2)):
while len(stack) > 0 and nums2[i] > nums2[stack[-1]]:
if nums2[stack[-1]] in nums1:
num1_index = nums1.index(nums2[stack[-1]])
res[num1_index] = nums2[i]
stack.pop()
stack.append(i)
return res