leetcode 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] 是如上所述的 下一个更大元素 。
示例：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

• 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
• 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
• 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

题解：
第一遍自己的解法，先找到和nums1元素相等的nums2中的索引，然后用队列先入先出的方法去解

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        queue = deque()
        for index1, num1 in enumerate(nums1):
            for index2, num2 in enumerate(nums2):
                if num1 == num2:
                    index_equal = index2
                    break
            for index2, num2 in enumerate(nums2):
                if index2 > index_equal:
                    queue.append(num2)
            flag = 0
            #这也可以不用break，把flag变成False大于就置True，用while len(queue) != 0 and flag==False: 
            while len(queue) != 0:  
                tmp = queue.popleft()
                if tmp > num1:
                    flag = 1
                    result.append(tmp)
                    break
            if flag == 0:
                result.append(-1)
            queue = deque()
            flag = 0
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

优化解法：用两个栈来解决，设定一个max变量，从后往前遍历，如果遍历过程中有大于num1的元素，则将max替换为当前遍历的这个元素，因为这样替换始终能保证max是离相等值最近的那个元素。然后因为遍历栈时会删除元素，所以用一个临时栈存储删除的元素，最后又把临时栈的元素给放回栈里去，保证栈的元素在遍历完后依旧完整。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        stack = []
        for i in nums2:
            stack.append(i)
        for num1 in nums1:
            tmp = []
            isfound = False
            max = -1
            while len(stack)!=0 and isfound==False:
                top = stack.pop()
                if top > num1:
                    max = top
                elif top==num1:
                    isfound = True
                tmp.append(top)
            result.append(max)
            while len(tmp) != 0:
                stack.append(tmp.pop())
        return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22