leetcode | 496.下一个更大元素

496.下一个更大元素

题目描述

给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

题目链接

思路

1.暴力解法
对于每一个 nums1[i] 中的元素，先在 nums2 中找到它，然后向右遍历找到第 1 个大于 nums1[i] 的元素。
2.单调栈
步骤：
1）使用单调栈先对 nums2 中的每一个元素，求出它的右边第一个更大的元素；
2）将上一步的对应关系放入哈希表（HashMap）中；
3）再遍历数组 nums1，根据哈希表找出答案。
维护单调栈：
我们维护的栈恰好保证了单调性：栈中的元素从栈顶到栈底是单调不降的。
当我们遇到一个新的元素 nums2[i] 时，我们判断栈顶元素是否小于 nums2[i]，
如果是，那么栈顶元素的下一个更大元素即为 nums2[i]，我们将栈顶元素出栈。
重复这一操作，直到栈为空或者栈顶元素大于 nums2[i]。此时我们将 nums2[i] 入栈，
保持栈的单调性，并对接下来的 nums2[i + 1], nums2[i + 2] … 执行同样的操作。

代码

class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        暴力解法
        对于每一个 nums1[i] 中的元素，先在 nums2 中找到它，然后向右遍历找到第 1 个大于 nums1[i] 的元素。

        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        # 使用内置方法list.index()/list.append()
        # next_greater_index = []  # 存储下一个更大元素下标的列表
        #
        # if len(nums1) < 1:
        #     return next_greater_index
        #
        # for num in nums1:  # 遍历nums1中的每一个元素
        #     index = nums2.index(num)  # 定位nums1中的元素在nums2中的下标
        #     for i in range(index+1, len(nums2)):  # 遍历nums1中元素在nums2中所在位置之后的元素
        #         if nums2[i] > num:  # 如果找到比nums1中元素更大的元素，则将下标加入下标列表
        #             next_greater_index.append(nums2[i])
        #             break
        #     else:
        #         next_greater_index.append(-1)
        #
        # return next_greater_index

        # 不使用内置方法list.index()/list.append()
        len1 = len(nums1)
        len2 = len(nums2)

        res = list()

        if len1 < 1:
            return res

        for i in range(len1):
            cur_val = nums1[i]
            j = 0
            while j < len2 and nums2[j] != cur_val:
                j += 1

            # nums2[j] = nums1[i]
            j += 1
            while j < len2 and nums2[j] < cur_val:
                j += 1

            if j == len2:
                res[i] = -1
                continue

            res[i] = nums2[j]
        return res

    def nextGreaterElement1(self, nums1, nums2):
        """
        栈（单调栈）

        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        stack = list()
        map = {}
        # 对nums2中的每一个元素，求出它的右边第一个更大的元素；
        # 将对应关系放入哈希表（HashMap）中
        for i in range(len(nums2)):
            while len(stack) != 0 and stack[-1] < nums2[i]:
                map[stack.pop()] = nums2[i]

            stack.append(nums2[i])

        # 遍历数组nums1，根据哈希表找出答案
        res = list()
        for j in range(len(nums1)):
            res.append(map.get(nums1[j], -1))

        return res


if __name__ == "__main__":
    slt = Solution()

    res_list = slt.nextGreaterElement1([4, 1, 2], [1, 3, 4, 2])

    print(res_list)