在Java中计算（不设计！）堆栈的最小值

我想写一个函数来计算（不是设计）给定堆栈的最小值。我认为我可以在网上轻松找到，但我发现没有什么。我发现的所有内容都是如何用getMinimum函数设计堆栈。在Java中计算（不设计！）堆栈的最小值

不同之处在于，当您设计这样的堆栈时，您将逐步构建堆栈（推送和弹出）并在任何操作后更新最小值。我在想，如果你有一个给定的堆栈，并且你想计算这个堆栈的最小值，那么你如何处理这个堆栈呢？也许，我没有很好的理由，或者我问自己错误的答案，或者我不太了解堆栈的概念，但是让我感到惊讶的是，在网络中没有找到任何答案，甚至在很多搜索...

这里是我的尝试：

public static int min(Stack stack){ 
     Stack temp = new Stack(); 
     int result = Integer.MAX_VALUE; 
     while(!stack.isEmpty()) { 
       int value = stack.pop(); 
       temp.push(value); 
       result = (result >= value)? value : result; 
      } 
    //stack is empty now, I have to recuperate it from the temp stack 
      while(!temp.isEmpty()) { 
        stack.push(temp.pop()); 
      } 

      return result; 
     }

在这段代码中，我用我自己的堆栈和节点实施。但正如你所看到的，代码非常简单。我写这篇文章主要是因为我问了很多关于这个问题的问题。

特别是，我想问问你请了三个主要问题：

是什么时候和这个功能的空间复杂度？我认为这是O（N），是不是？我在计划中总会遇到一些困难。它通常是O（2 * N）（它等于O（N）），因为我们运行每个节点的堆栈节点。
我的方法是否合乎逻辑？据我所知，如果你想获得栈中第k个元素的访问权限，你必须弹出k-1之前的元素。或者在这里，我认为，如果我们只想调整其最小值（如果您想再次操作同一个堆栈），那么弹出整个堆栈是绝对不合逻辑的。这就是为什么我做了第二个while循环来保持堆栈处于原始状态。
也许，我们可以制作一个堆栈的副本，但是我读到用java编写克隆对象并不那么容易，我想知道这样的一个小函数是否会消耗很多？

感谢

来源

2016-05-07 salamanka44

另外，如果你不想修改“addToStack”功能，你真的不能让这个分功能更好，所以是您的解决方案我也会尝试。我也想说，复杂性是O（n） – Dodekeract

恩，我在我的IDE中尝试过，它的工作原理。但说实话，这不是真正的计算分钟（它可以是最大或其他）。它更多的是了解堆栈概念背后的概念和效用:) – salamanka44

是的，是的，是的（不要使用克隆，永远，我怀疑你的攻击类实现它合理）。这在代码审查方面确实会更好，但总体思路是正确的。 – Voo

时间和空间确实为O（n）为你解释。
你的方法中有逻辑。但是，您可以以允许您实现peek（int index）的方式实现堆栈 - （例如，如果您的堆栈基于数组），然后不必在插入所有元素时弹出。
您可以在您的Stack实现中保存额外的排序数据结构，这将允许您获取O（1）中的最小值，但会使用的空间加倍。最后，它总是在空间和时间之间进行权衡。

来源

2016-05-07 18:42:29 aviad

这将是使用递归轻松了不少：

int min(Stack stack) { 
    if(stack.isEmpty()) 
     return Integer.MAX_VALUE; 

    int temp = stack.pop(); 
    int min = Math.min(temp, min(stack)); 
    stack.push(temp); 

    return min; 
}

来源

2016-05-07 18:44:30

这个解决方案在使用巨大堆栈时不会破坏吗？难道这不容易导致“太多的递归”错误？ – Dodekeract

@Dodekeract当然，CS中没有免费的午餐。 –

在我看来，一个更好的选择将是利用Vector能力作为Stack是Vector在Java中

public static int min(Stack<Integer> stack) { 
    Integer[] elements = stack.toArray(new Integer[1]); 
    int min = Integer.MAX_VALUE; 
    for(int i=0;i<elements.length;i++) { 
     if(elements[i] < min) { 
      min=elements[i]; 
     } 
    } 
    return min; 
}

一个子类

这将使您通过自己实施的方法获得更大的输入数据性能。

希望这会有所帮助。

来源

2016-05-07 18:46:38 Sanjeev

我正要说同样的事情...... – selbie

一个更正。我不认为'[]'运算符被重载。而不是'elements [i]'说，'elements.get（i）' – selbie

它的一个数组和数组只能用'[]'来访问。请看第一行。 – Sanjeev

Java中的Stack类继承自Vector。因此，您可以枚举项目而无需执行任何推送，弹出或复制操作。有了这样说，这里是一个O（N）解决方案：

public static int min(Stack stack) { 
    int m = Integer.MAX_VALUE; 
    for (int i = 0; i < stack.size(); i++) { 

     int current = stack.get(i).intValue(); 

     if (current < m) 
     { 
      m = current; 
     } 
    } 
    return m; 
}

来源

2016-05-09 01:47:42 selbie

在Java中计算（不设计！）堆栈的最小值

回答

相关问题