给定一个唯一的正整数数组，为每个元素找到最接近的较小元素，但距离至少为 k

Question

我所指的问题与此类似。唯一的区别是 1.）从当前元素到我们选取的最接近的较小元素，应该至少有"k"个单位的距离。2.） 可以从任一方向（向左或向右）选取元素。例如，如果 k=4 并且当前元素旁边有一个较小的元素，我们无法选择它，因为它太近了。

我尝试以与其他解决方案相同的方式实现它。我所做的更改是，每次从堆栈中删除一个元素时，如果它实际上比当前元素小，但只是因为它比 k 个单位更接近而被删除，那么一旦找到当前元素的答案，我就会将该元素添加回堆栈，然后继续下一个元素。这似乎有效，但我相信有一种更有效的方法来解决这个问题。任何建议都会非常有帮助。

Answer 1

运行时和空间复杂度为 O（n） 的解决方案

仅向前遍历：以下算法是对给定数组的答案的修改，找出每个元素的下一个较小元素，并为输入数组的每个元素返回最接近的较小后继元素，并保证元素和后继元素之间的最小距离：

// Traversal in forward direction only:
function smaller(array, distance) {
    var length = array.length,
        result = new Array(length).fill(null),
        stack = [];
    
    // Forward pass:
    for (var i = 0, j = distance; j < length; ++i, ++j) {
      while (stack.length > 0 && array[j] < array[stack[stack.length - 1]]) {
        result[stack.pop()] = array[j];
      }
      stack.push(i);
    }
    return result;
}
console.log(smaller([0, 2, 1], 0)); // [null, 1, null]
console.log(smaller([5, 2, 1, 7, 6, 0], 1)); // [1, 0, 0, 0, null, null]

向前和向后遍历：以下算法为输入数组的每个元素返回最近的较小后继或前置元素，并保证元素与后继或前置元素之间的最小距离。

它的工作方式与第一种算法类似，但沿两个方向遍历数组并存储索引，而不是较小元素的值。最接近的较小元素是从最后第三遍的两次走刀的结果中选择的：

// Traversal in both directions:
function smaller(array, distance) {
    var length = array.length,
        forward = new Array(length).fill(null),
        backward = new Array(length).fill(null),
        stack = [];
  
    // Forward pass:
    for (var i = 0, j = distance; j < length; ++i, ++j) {
      while (stack.length > 0 && array[j] < array[stack[stack.length - 1]]) {
        forward[stack.pop()] = j;
      }
      stack.push(i);
    }
    // Backward pass:
    stack = [];
    for (var i = length - 1, j = length - distance - 1; j >= 0; --i, --j) {
      while (stack.length > 0 && array[j] < array[stack[stack.length - 1]]) {
        backward[stack.pop()] = j;
      }
      stack.push(i);
    }
    
    // Pick closest elements from both passes:
    for (var i = 0; i < length; ++i) {
      if (backward[i] !== null) {
        if (forward[i] !== null && forward[i] - i < i - backward[i]) {
          forward[i] = array[forward[i]];
        } else {
          forward[i] = array[backward[i]];
        }
      } else if (forward[i] !== null) {
        forward[i] = array[forward[i]];
      } 
    }
    return forward;
}
console.log(smaller([0, 2, 1], 0)); // [null, 0, 0]
console.log(smaller([5, 2, 1, 7, 6, 0], 1)); // [1, 0, 0, 2, 1, null]