[JavaScript 刷题] 栈 - 下一个更大元素 I, leetcode 496

github repo 地址: https://github.com/GoldenaArcher/js_leetcode，Github 的目录 大概 会更新的更勤快一些。

题目地址：496. Next Greater Element I

题目

如下：

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

解题思路

easy 的题目暴力解可用：遍历 nums1 并找到 nums2 中比它大的数字，这个的时间复杂度最大为 $O(n^2)$。

另一种解法是使用单调栈去解决。

以下面两个数组作为例子：num1 = [1, 3, 8], nums2 = [3, 2, 1, 8]，其核心思想就是在遇到 stack[stack.length - 1] > curr 的情况下，将值持续性的压入栈中。当遇到 stack[stack.length - 1] < curr 时进行弹栈操作。

在这个前提下，栈中的最初几个遍历值为 [3, 2, 1]，当遇到 8 时，就可以进行弹栈操作。对于 1, 2, 3 来说，下一个最大数字都是 8. 随后将 8 压入栈中，此时数组完成遍历，不可能存在比 8 更大的数字，因此，将 nums 中 8 所在的下标标记为 -1。

这样每次弹出的数值一定是一个递增或是递减的状态，留在栈中的值也会呈现一个递增或递减的状态，这样的设计结构在寻找下一个最大/最小值时最为适用。

单调栈的模板为：

for (let i = 0; i < arr.length; i++) {
  const curr = arr[i];

  while (stack.length && stack[stack.length - 1] > curr) {
    stack.pop();
  }

  stack.push(curr);
}
1
2
3
4
5
6
7
8
9

使用 JavaScript 解题

暴力解

var nextGreaterElement = function (nums1, nums2) {
  const res = [];
  let found, nextMinIdx;

  for (let i = 0; i < nums1.length; i++) {
    const num = nums1[i];
    found = false;
    nextMinIdx = -1;

    for (let j = 0; j < nums2.length; j++) {
      if (nums2[j] === nums1[i]) {
        found = true;
        nextMinIdx = j;
        break;
      }
    }

    for (let j = nextMinIdx; j < nums2.length; j++) {
      if (nums2[j] > nums2[nextMinIdx]) {
        res.push(nums2[j]);
        break;
      }
    }

    if (res.length !== i + 1) res.push(-1);
  }

  return res;
};
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
26
27
28
29

单调栈

var nextGreaterElement = function (nums1, nums2) {
  const res = [];
  let found, nextMinIdx;

  const map = {};

  for (let i = 0; i < nums1.length; i++) {
    map[nums1[i]] = i;
  }

  const stack = [];

  for (let i = 0; i < nums2.length; i++) {
    const curr = nums2[i];

    while (stack.length && curr > stack[stack.length - 1]) {
      const val = stack.pop();
      if (map[val] !== undefined) {
        res[map[val]] = curr;
      }
    }

    stack.push(curr);
  }

  for (const val of stack) {
    if (map[val] !== undefined) res[map[val]] = -1;
  }

  return res;
};
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
26
27
28
29
30
31