javascript中2D数组中相同的索引值之和

Question

在解决了问题之后，我得出了这个结论。

let n = 10;
let array = [
  [1, 5, 3],
  [4, 8, 7],
  [6, 9, 1]
];
let answer = array.map((val) => new Float32Array(n).fill(val[2], val[0] - 1, val[1]));
console.log(Math.max(...answer.reduce((r, a) => a.map((b, i) => (r[i] || 0) + b), [])))

好的，它创建了一个n元素数组，第三个元素的值来自索引的第一个值到第二个值的范围。

索引从这里的1开始。

与[1, 5, 3]一样(n = 10)，它创建了一个由10个元素组成的数组，其值为3，从索引1到索引5，否则一切都是空的或0。

然后，对于[4, 8, 7]，(n = 10)，它创建一个从索引4到索引8的值为7的10个元素数组，否则，一切都是空的或0。

然后，对于[6, 9, 1]，(n = 10)，它创建一个从索引6到索引9的值为1的10个元素数组，否则，一切都是空的或0。

现在我们必须对所有匹配的列进行求和，并返回最大值，我这样做的方法是

Math.max(...answer.reduce((r, a) => a.map((b, i) => (r[i] || 0) + b), []))

一切都很好，测试用例也能工作，但是程序根本没有效率，请参考这个问题，我的代码只是超时。

我认为问题是当我把这些值相加时。这就是占用最多记忆的地方。

有什么方法可以对相同的索引数组值进行求和呢？因为它是最有效的

Answer 1

问题是，您为每个操作(在输入数组中)创建一个长度为n的数组，然后通过对结果调用reduce来对它们进行求和，然后您最终找到该结果数组的最大值。但是，您只需要一个初始数组进行加和，就可以在相同的操作中找到最大值--这里是一个相当冗长的表单：

function arrayManipulation(n, arr) {
  var res = [];
  var max = 0;

  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < n; j++) {
      if (i === 0) {
        res.push(j >= arr[i][0] - 1 && j <= arr[i][1] - 1 ? arr[i][2] : 0);
      }
      else {
        res[j] += j >= arr[i][0] && j <= arr[i][1] ? arr[i][2] : 0;
      }
      max = Math.max(max, res[j]);
    }
  }
  return max;
}

它可以缩小到更简洁的形式：

function arrayManipulation(n, arr) {
  var res = [];
  var max = Number.MIN_VALUE;

  for (var i = 0; i < arr.length; i++) {
    for (var j = arr[i][0]; j <= arr[i][1]; j++) {
      res[j] = (res[j] || 0) + arr[i][2];
      max = Math.max(max, res[j]);
    }
  }
  return max;
}

这里使用的是，它只需要遍历由输入数组中的每个操作实际操作的数组的间隔。例如，在示例操作中，对于第一个操作，只需将3添加到从1到5包含的位置的值。

更新

根据weegee的评论，对我上面的解决方案进行修改，可以解决以下问题：

function arrayManipulation(n, arr) {
  arr = arr.sort((a, b) => a[0] < b[0] ? -1 : a[0] === b[0] ? 0 : 1);
  var max = Number.MIN_VALUE;

  for (var i = 0; i < arr.length; i++) {
    var sum = arr[i][2];
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j][0] <= arr[i][1])
        sum += arr[j][2];
      else
        break;
    }
    max = Math.max(sum, max);
  }

  return max;
}

首先，根据操作的起始位置(子数组中的第一个元素)对操作进行排序，然后，在操作与操作之间存在重叠的情况下，迭代和总结操作。最后，将当前和与max中现有的最大和进行了比较。