739、每日温度:
class Solution(object):
def dailyTemperatures(self, temperatures):
"""
:type temperatures: List[int]
:rtype: List[int]
"""
stack = []
res = [0] * len(temperatures)
stack.append(0)
for i in range(1, len(temperatures)):
if temperatures[i] <= temperatures[stack[-1]]:
stack.append(i)
else:
while stack and temperatures[i] > temperatures[stack[-1]]:
res[stack[-1]] = i - stack[-1]
stack.pop(-1)
stack.append(i)
return res
用单调栈确实很巧妙,因为是记录到更高温度的天数,因此相当于要求第一个大于当前数值的元素,从栈顶到栈底就是单调递增的
496、下一个更大元素I:
class Solution(object):
def nextGreaterElement(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
stack = [0]
res = [-1] * len(nums1)
hash_map = {}
for i, v in enumerate(nums1):
hash_map[v] = i
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 hash_map:
index = hash_map[nums2[stack[-1]]]
res[index] = nums2[i]
stack.pop(-1)
stack.append(i)
return res
求下一个更大元素,本题的技巧在于先建立nums1的元素值到下标的映射,方便nums2在遍历过程中寻找到index,注意stack.pop的作用域,无论nums2[stack[-1]]是否在map里,都是要pop掉的stack[-1]的