在 JavaScript 中使用堆栈查找下一个更大的元素

发布于09月18日

我正在熟悉Stack，虽然我能够想出一种逻辑，使我在大多数情况下都有问题，但我遇到的问题很少.

console.log(greaterL([56, 23, 1, 5, 18, 17]))//[-1, -1, 5, 18, -1, -1]

====> actually returns -1, 5, 18, -1, -1, -1

console.log(greaterL([70, 60, 1, 4, 8, 12, 50, 23]))//[-1,-1, 4, 8, 12, 50, -1, -1]

====> actually returns -1, 4, 8,12, 50, -1, -1, -1

function greaterL(arr){   
    let stack = []
    let result = []
     for(let i = 0; i < arr.length-1; i++){
        stack.push(arr[i])
        let next = arr[i+1]
        
        while(stack.length!==0 && stack[stack.length-1] < next){
            stack.pop();
            result.push(next);          
         }             
    }
    result.push(-1)
    
    while(stack.length){
       let value = stack.pop()
       
        if(arr[0]===value){
            result.unshift(-1)
        }else{
            result.push(-1)
        }
        
    }
    
    return result
}

我知道我已经很接近了，但我不能想出一个能满足所有情况的解决方案，如果有人能为我指出正确的方向，我将不胜感激

推荐答案

我将从末尾循环数组，这看起来更自然，因为我们 for each 数组项分析数组的其余部分.

因此，我们可以同时循环和收集堆栈.

所以我们收集堆栈中的值，除非我们发现一个比堆栈中更大的值.在这种情况下，我们只需将堆栈重置为此值，并继续循环到开头.

在这种情况下，我实际上不会将堆栈称为堆栈，因为不需要从堆栈中弹出/移位元素.

console.log(...greaterL([56, 23, 1, 5, 1, 5, 1,18, 17]))//[-1, -1, 5, 18, -1, -1]
console.log(...greaterL([70, 60, 1, 4, 8, 12, 50, 23]))//[-1,-1, 4, 8, 12, 50, -1, -1]

function greaterL(arr){
  
  let stack = [arr[arr.length - 1]];
  const result = [-1];
  
  for(let i = arr.length - 2; i >= 0; i--){
    const item = arr[i];
    const found = stack.find(max => max > item);
    result.unshift(found ?? -1);
    found === undefined ? stack = [item] : stack.unshift(item);
  }
  
  return result;
}

关于堆栈代码，当您try 将-1放入没有下一个最大值的数组项时，会出现问题.你实际上应该收集这些项目的索引，并在记忆中的索引处插入-1.

但使用堆栈的整个 idea 似乎都是无效的.它假设连续的项目将比之前的项目更大.一旦我添加了更多的数据，算法就失败了.因此，我的反向循环似乎是这两个 Select 中唯一合适的 Select .

console.log(...greaterL([56, 23, 1, 5, 1, 5, 1,18, 17]))//[-1, -1, 5, 18, -1, -1]
console.log(...greaterL([70, 60, 1, 4, 8, 12, 50, 23]))//[-1,-1, 4, 8, 12, 50, -1, -1]

function greaterL(arr){   
  
  let stack = []
  let result = []
  
   for(let i = 0; i < arr.length-1; i++){
      stack.push([arr[i], i])
      let next = arr[i+1]

      while(stack.length!==0 && stack[stack.length-1][0] < next){
          stack.pop();
          result.push(next);          
       }             
  }
  result.push(-1);
  stack.forEach(([_, idx]) => result.splice(idx, 0, -1));

  return result
}

在 JavaScript 中使用堆栈查找下一个更大的元素

推荐答案

Javascript相关问答推荐

JavaScript替换子 node 导致它们更改为[对象HTMLTable SectionElement]

如何使用3个部件之间的路由？

我无法使用tailwind-css和reactJS修改图像的位置

将音频记录从js发送到activx-web服务器以保存到磁盘

追踪执行顺序

React存档iframe点击行为

Angular中计算信号和getter的区别

react—router v6：路由没有路径

PrivateRoute不是路由组件错误

在react js中使用react—router—dom中的Link组件，分配的右侧不能被 destruct ''

空的结果抓取网站与Fetch和Cheerio

在带有背景图像和圆形的div中添加长方体阴影时的重影线

为什么useState触发具有相同值的呈现

第二次更新文本输入字段后，Reaction崩溃

如何将数组用作复合函数参数？

在开发期间，Web浏览器如何运行&qot；.jsx&qot；文件？

为什么可选参数的顺序会导致问题？

用另一个带有类名的div包装元素

JavaScript将字符串数字转换为整数

MongoDB通过数字或字符串过滤列表