代码随想训练营第58天（Python）｜ 739. 每日温度、496.下一个更大元素 I

739. 每日温度

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