javascript - 算法:Next Greater Element I(来自 leetcode)

Question

有人可以告诉我在解决这个算法时我遗漏了什么吗？我遇到的一个问题是嵌套循环内的第一个 if 语句没有求值，但我不知道它为什么不求值。

问题描述如下:

给你两个数组(没有重复项)nums1 和 nums2，其中 nums1 的元素是 nums2 的子集。在 nums2 的相应位置找到 nums1 的元素的所有下一个更大的数字。nums1 中数字 x 的下一个更大的数字是 nums2 中它右边的第一个更大的数字。如果不存在，则为这个数字输出-1。

示例 1:

输入:nums1 = [4,1,2], nums2 = [1,3,4,2]。

输出:[-1,3,-1]

解释: 对于第一个数组中的数字 4，您无法在第二个数组中找到下一个更大的数字，因此输出 -1。 对于第一个数组中的数字 1，第二个数组中它的下一个更大的数字是 3。 对于第一个数组中的数字 2，第二个数组中没有下一个更大的数字，因此输出 -1。

link to original description

到目前为止，这是我的代码:

 var nums1 = [4,1,2];
 var nums2 = [1,3,4,2];

  var nextGreaterElement = function(findNums, nums) {
    var holder = [];

    for (var i = 0; i < findNums.length; i++) {

     //loop through the 2nd array starting at the index of the first loop's current item. 

      for (var j = nums.indexOf(findNums[i]); i < nums.length - j; i++) {

        if (nums[j+1] > nums[j]) {
          holder.push(nums[j+1]);
          break;
        } 

        if (nums[nums.length]) {
          holder.push(-1);
        }
      }
    }
    return holder;
};

nextGreaterElement(nums1, nums2)

感谢您的帮助。

Answer 1

问题:在内部循环(j 循环)中更新变体 i，但不更新变体 j

缺失:调试工作

---

问题描述

理论上，您的代码设计应该将 nums1 中的每个值与 nums2 的相关部分进行比较。因此，它将转向外层 for 循环以在 nums1 上循环，并转向内层 for 循环以在外层 for 循环的每次迭代中循环 nums2 的相关部分.

在您的代码中，变体 i 是 findNums 的索引指针(即 nums1)，而变体 j 是 nums 的索引指针(即 nums2)。变体 i 总是在内部 for 循环和外部 for 循环中更新，而变体 j 在外部 for 循环的每次迭代中设置一次。这与您应该做的事情相矛盾。

调试(您遗漏的工作)

找一张纸和一支笔。坐下来，试运行程序并不断记录相关信息(变体 i、变体 j、findNums[i]、nums[j]、...)，您可以弄清楚为什么您的代码无法正常工作。

---

可能的解决方案

var nextGreaterElement = function(findNums, nums) {
    var holder = [];

    for (var i = 0; i < findNums.length; i++) {
      var hasNextGreaterElement = false;
      // try to serach for next greater element
      for (var j = nums.indexOf(findNums[i])+1; j < nums.length; j++) {
        // handle case for next greater element is found
        if (nums[j] > findNums[i]) {
          holder.push(nums[j]);
          hasNextGreaterElement = true;
          break;
        }
      }
      // handle case for next greater element is not found
      if (!hasNextGreaterElement) {
          holder.push(-1);
      }
    }
    return holder;
};

var findNums=[4,1,2];
var nums=[1,3,4,2];
console.log(nextGreaterElement(findNums, nums));