SONG Shengjie
单调栈 Monotonic Stack(1)
List: 739. 每日温度，496.下一个更大元素，503.下一个更大元素II
739. 每日温度daily-temperatures，496.下一个更大元素 Inext-greater-element-i，503.下一个更大元素IInext-greater-element-ii
739. 每日温度daily-temperatures
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
st = []
result = [0] * len(temperatures)
st.append(0)
for i in range(1, len(temperatures)):
if temperatures[i] <= temperatures[st[-1]]:
st.append(i)
else:
while st and temperatures[i] > temperatures[st[-1]]:
result[st[-1]] = i - st[-1]
st.pop()
st.append(i)
return result
496.下一个更大元素 Inext-greater-element-i
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
st = []
result = [-1] * len(nums1)
st.append(0)
for i in range(1, len(nums2)):
if nums2[i] <= nums2[st[-1]]:
st.append(i)
else:
while st and nums2[i] > nums2[st[-1]]:
if nums2[st[-1]] in nums1:
result[nums1.index(nums2[st[-1]])] = nums2[i] #找元素-找下标-记录值
st.pop()
st.append(i)
return result
503.下一个更大元素IInext-greater-element-ii
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
st = []
result = [-1] * len(nums)
st.append(0)
for i in range(1, len(nums) * 2):
if nums[i % len(nums)] <= nums[st[-1]]:
st.append(i % len(nums))
else:
while st and nums[i % len(nums)] > nums[st[-1]]:
result[st[-1]] = nums[i % len(nums)]
st.pop()
st.append(i % len(nums))
return result
注意要存的是什么！