列码山阵

Question

我一直在做列码上最长的山列：

如果以下属性保持不变，让我们将任何(相邻的)子数组B(A的)称为山：

• B.length >= 3
• 存在一些0 < i < B.length - 1，例如B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(注意B可以是A的任何子数组，包括整个数组A)给定一个整数数组A，返回最长山的长度。如果没有山，返回0。例如:输入：2 1 4 7 3 2 2 5 输出: 5 解释:最大的山是长度为5的1,4,7,3,2。

我已经想出了一个解决方案，它通过了测试，但只超过了17%的javascript提交。我只想知道我的代码是否可以用来优化它的性能。此外，请告诉我，如果代码可以写得更好。

这个想法如下。在山脉阵列中，我们有一个起点、一个高峰和一个终点。我记录着一座山什么时候开始，什么时候山峰，什么时候山结束。当山结束时，我从开始堆栈中弹出我的开始值，并使用扩展操作符将其添加到包含山的峰值和结束的结果数组中。

例如数组1,3,8..。山从索引1开始，高峰在索引3，结束在索引8。为了找到数组的长度，我从开始减去结束。

一座山可以有多个峰，因此一个数组(如[1,3,8，8,13,18] )是可能的。在处理这种情况时，我使用一个maxDifference变量来存储如果山区是完整的开始，高峰，结束，则最大的差异。

var longestMountain = function(A) {

    let maxDifference = 0;
    let startPeakEnd = [];
    const start = [];
    const innerLoop = [];

    if(A[1]>A[0])start.push(0)
    else start.push(1);

    for(let i = 0; i < A.length; i++){
        if(A[i-1]<A[i] && A[i+1]<A[i]){
            startPeakEnd.push(i);
        }else if(A[i-1]>=A[i] && A[i+1]>=A[i]){
            startPeakEnd.push(i);
            innerLoop.push([start.pop(),...startPeakEnd]);
            start.push(i)
            startPeakEnd = [];
        }else if(A[i+1]===undefined){
            startPeakEnd.push(i);
            innerLoop.push([start.pop(),...startPeakEnd]);
        }
    }

    for(let item of innerLoop){
        if(item.length===3){
            if(item[2]-item[0]+1>maxDifference){
                maxDifference=item[2]-item[0]+1;
            }
        }
    }

    return maxDifference;

};

Answer 1

最好尝试并使用内置的函数来迭代数组。看来你正在尝试生成和存储所有可能的山脉。这是不必要的。这将是我的方法。

var longestMountain = function(arr) {
  //get nodes that may be the peaks of mountains
  var candidates = arr.map(function(currentValue, index) {
    if (index == 0 || index === arr.length - 1) {
      return false;
    } else {
      return arr[index - 1] < currentValue && arr[index + 1] > currentValue;
    }
  });

  //for each index, calculate the height of the slope where arr[i - 1] < arr[i]
  var increasingMountainCounts = arr.map(function(currentValue, index) {
    if (index == 0 || arr[index - 1] >= currentValue) {
      return 0;
    } else {
      return arr[index - 1] + 1;
    }
  });

  //for each index, calculate the height of the slope where arr[i - 1] > arr[i]
  var decreasingMountainCounts = arr.reverse().map(function(currentValue, index) {
    if (index == 0 || arr[index - 1] >= currentValue) {
      return 0;
    } else {
      return arr[index - 1] + 1;
    }
  });

  //for each candidate peak, get the height of the mountain with that peak
  var maxMountainHeight = 0;

  candidates.forEach(function(currentValue, index) {
    if (currentValue !== true) {} else {
      maxMountainHeight = Math.max(maxMountainHeight, increasingMountainCounts[index - 1] + decreasingMountainCounts[index + 1] + 1);
    }
  });

  return maxMountainHeight;

};

另一种方法是使用更多的javascript数组迭代器，但在我看来，这会降低代码的可读性。

var longestMountain = function(arr) {
  var candidates = arr.map(function(currentValue, index) {
    if (index == 0 || index === arr.length - 1) {
      return false;
    } else {
      return arr[index - 1] < currentValue && arr[index + 1] > currentValue;
    }
  });

  var increasingMountainCounts = arr.map(function(currentValue, index) {
    if (index == 0 || arr[index - 1] >= currentValue) {
      return 0;
    } else {
      return arr[index - 1] + 1;
    }
  });

  var decreasingMountainCounts = arr.reverse().map(function(currentValue, index) {
    if (index == 0 || arr[index - 1] >= currentValue) {
      return 0;
    } else {
      return arr[index - 1] + 1;
    }
  });

  var maxMountainHeightAccumulator = (maxMountainHeight, currentValue, index) => {
    if (currentValue !== true) {
      return maxMountainHeight;
    } else {
      return Math.max(maxMountainHeight, increasingMountainCounts[index - 1] + decreasingMountainCounts[index + 1] + 1);
    }
  };

  return candidates.reduce(maxMountainHeightAccumulator, 0);

};

在提高性能方面，这让我想起了寻找具有最大和/积的(连续)子序列的问题。该解决方案可能需要完全重写您的代码。