496. 下一个更大元素 I

https://leetcode-cn.com/problems/next-greater-element-i/

解法一：暴力hash

为nums2建立一个map < int, int> ,key为num2各元素的值,value为元素下标. 然后遍历nums1,对其中每个元素nums1[i],找到其在nums2对应元素j,然后从j向后搜索,找到第一个大于j的就记录,为节省空间,可以直接写入nums1[i] (反正一次遍历,以后也不会再用到). 遍历结束后nums1就是输出.

//cpp
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            hash[nums[i]] = i;//建立hash映射
        }
        for (int i = 0; i < findNums.size(); i++) {
            int index = hash[findNums[i]];
            int j;
            for (j = index+1; j < nums.size(); j++) {
                if (nums[j] > nums[index]) {
                    findNums[i] = nums[j];
                    break;//找到就立即跳出本层循环
                }                
            }
            if (j >= nums.size()) findNums[i] = -1;//若没找到,则为-1
        }
        return findNums;
    }
};

解法二：栈+hash

栈用来存储需要找到下一个最大元素的元素。

首先第0号元素入栈，从1号开始遍历nums2，遇到比栈顶大的元素i就将键值对<栈顶，i>写入hash，并将栈顶出栈，直到栈空或者i不大于栈顶，遍历结束就得到<元素，下一个较大元素>的hash。

一次遍历nums1，在hash中查找输出即可。

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if not nums1 or not nums2:  #有一个为空
            return []
        stack = [nums2[0]]  #栈初始
        hash = {}   #hash表
        for num in nums2[1:]:
            while len(stack) > 0 and num > stack[-1]:
                hash[stack[-1]] = num
                stack.pop()
            stack.append(num)
        #处理输出
        res = []
        for num in nums1:
            if num in hash:
                res.append(hash[num])
            else:
                res.append(-1)
        return res

2021.10.26

class Solution:
    def nextGreaterElement(self, nums1, nums2)  :
        stack = [nums2[0]]
        n,m = len(nums1), len(nums2)
        hash = {}
        for i in range(1,m):
            while len(stack) > 0 and nums2[i] > stack[-1]:
                num = stack.pop()
                hash[num]  = nums2[i]
            stack.append(nums2[i])
        res = [-1]* n
        for j in range(n):
            if nums1[j] in hash:
                res[j] = hash[nums1[j]]
        return res

解法三:单调栈

从后往前遍历nums2,元素下标依次入栈,元素下标依次入栈，构造一个单调栈，保持栈底最大，栈顶最小。每次i与栈顶比较，若t[i]大于等于栈顶则弹栈，即栈顶是最靠近i的最大元素(下标).

当a = nums2[i]也在nums1中,取栈顶指示的数b, 则b就是a的右边第一个更大值

n, m = len(nums1), len(nums2)
hash = {}   #映射nums1每个元素的<值，下标>
for i in range(n):
    hash[nums1[i]] = i
res = [-1] * n
stack = []  #放的是下标
for i in range(m-1, -1, -1):
    while stack and nums2[stack[-1]] < nums2[i]:
        stack.pop()
    if nums2[i] in hash:
        index = hash[nums2[i]]
        res[index] = nums2[stack[-1]] if stack else -1
    stack.append(i)
return res