Powered by:NEFU AB-IN

Link

496. 下一个更大元素 I

• 题意

  nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
  给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
  对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
  返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

• 思路

  求每一个数的右边离他最近的最大数是什么，即从后往前遍历，用单调栈先把小的弹出去

• 代码

  class Solution:
      def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
          stk, res = [], []
          d = Counter()
          for i in range(len(nums2) - 1, -1, -1):
              while stk and stk[-1] <= nums2[i]:
                  stk.pop()
              d[nums2[i]] = stk[-1] if stk else -1
              stk.append(nums2[i])
          for i in nums1:
              res.append(d[i])
          return res