496.下一个更大元素I

链接：496.下一个更大元素I
难度：Easy
标签：栈、数组、哈希表、单调栈
简介：请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

题解 1 - typescript

• 编辑时间：2021-07-20
• 执行用时：76ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：单调递减栈。

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const map: Record<number, number> = {};
  const n2 = nums2.length;
  for (let i = 0; i < n2; i++) map[nums2[i]] = i;
  const stack: number[] = [];
  const arr = new Array(n2).fill(-1);
  for (let i = 0; i < n2; i++) {
    const num = nums2[i];
    while (stack.length && nums2[stack[stack.length - 1]] < num) arr[stack.pop()!] = num;
    stack.push(i);
  }
  return nums1.map(num => arr[map[num]]);
}

题解 2 - typescript

• 编辑时间：2021-10-26
• 执行用时：76ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：单调栈。

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const map = new Map<number, number>();
  nums1.forEach((v, i) => map.set(v, i));
  const ans: number[] = new Array(nums1.length).fill(-1);
  const stack: number[] = [];
  for (const num2 of nums2) {
    while (stack.length && stack[stack.length - 1] < num2) {
      const num = stack.pop()!;
      if (map.has(num)) ans[map.get(num)!] = num2;
    }
    stack.push(num2);
  }
  return ans;
}