java 如何在不使用 max() 或迭代的情况下在堆栈中查找最大整数值？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17841522/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to Find the Max Integer Value in a Stack without using max() or iterating over it?
提问by c12
I was asked in an interview the following question: if you have a Stack of Integers how would you find the max value of the Stack without using Collections.max and without iterating over the Stack and comparing elements. I answered it with the below code as I don't know of another way than using any Collections API or iterating over the Stack and using comparisons. Any ideas?
我在一次采访中被问到以下问题：如果你有一个整数堆栈，你如何在不使用 Collections.max 并且不迭代堆栈和比较元素的情况下找到堆栈的最大值。我用下面的代码回答了这个问题，因为我不知道除了使用任何集合 API 或迭代堆栈并使用比较之外的其他方法。有任何想法吗？
import java.util.Collections;
import java.util.Stack;
public class StackDemo {
public static void main(String[] args){
Stack lifo = new Stack();
lifo.push(new Integer(4));
lifo.push(new Integer(1));
lifo.push(new Integer(150));
lifo.push(new Integer(40));
lifo.push(new Integer(0));
lifo.push(new Integer(60));
lifo.push(new Integer(47));
lifo.push(new Integer(104));
if(!lifo.isEmpty()){
Object max = Collections.max(lifo);
System.out.println("max=" + max.toString());
}
}
}
采纳答案by Luke
Edit:
编辑：
without iterating over the Stack
不迭代堆栈
does not actually prohibit alliteration. Rather, the question only prohibits doing the simple
实际上并没有禁止所有迭代。相反，这个问题只禁止做简单的
for (Integer i : lifo)
Thus, this solution satisfies the question's limitations.
因此，该解决方案满足问题的局限性。
Just empty a copy of the stack. pop each of the elements from the copy, checking for max against an integer all the while.
只需清空堆栈的副本。从副本中弹出每个元素，并始终根据整数检查 max。
Stack<Integer> lifoCopy = (Stack<Integer>) lifo.clone();
int max = Integer.MIN_VALUE;
while (!lifoCopy.isEmpty())
{
max = Math.max(lifoCopy.pop(), max);
}
System.out.println("max=" + max.toString());
This will work for you in O(n) time even if your interviewers decide to be more restrictive and not allow more built in functions (max, min, sort, etc.).
即使您的面试官决定更加严格并且不允许更多内置函数（最大值、最小值、排序等），这也会在 O(n) 时间内为您工作。
Additionally, if you need to have the original unharmed, but can't use clone, you can do so with an extra stack:
此外，如果您需要原件完好无损，但不能使用克隆，则可以使用额外的堆栈来实现：
Stack<Integer> reverseLifo = new Stack<Integer>();
int max = Integer.MIN_VALUE;
while (!lifo.isEmpty())
{
int val = lifo.pop();
max = Math.max(val, max);
reverseLifo.push(val);
}
while (!reverseLifo.isEmpty())
{
lifo.push(reverseLifo.pop());
}
System.out.println("max=" + max.toString());
Finally, this assumes that comparison against a temp variable is acceptable. If no comparison is allowed at all, then this solution in conjunction with this methodwill work.
最后，这假设与临时变量的比较是可以接受的。如果根本不允许比较，则此解决方案与此方法结合使用。
回答by DannyMo
By using Collections.min()instead:
Collections.min()改为使用：
if (!lifo.isEmpty()) {
Integer max = Collections.min(lifo, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
System.out.println("max=" + max.toString());
}
Note that the custom Comparatorflips the comparison so that Collections.min()will actually return the max.
请注意，自定义会Comparator翻转比较，以便Collections.min()实际返回最大值。
回答by enderland
import java.util.Collections;
import java.util.Stack;
public class StackDemo {
public static void main(String[] args) {
Stack lifo = new Stack();
lifo.push(new Integer(4));
lifo.push(new Integer(1));
lifo.push(new Integer(150));
lifo.push(new Integer(40));
lifo.push(new Integer(0));
lifo.push(new Integer(60));
lifo.push(new Integer(47));
lifo.push(new Integer(104));
System.out.println("max= 150"); // http://xkcd.com/221/
}
}
回答by Smit
Not sure will this satisfy your question need, but this way use of max()and iterationcould be avoided, anyhow sortdoes use iterationand Comparablein background.
不知道这会满足你的问题的需要，但这种方式使用的max()和iteration可避免的，无论如何sort不会使用iteration和Comparable背景。
if (!lifo.isEmpty()) {
Stack sc = (Stack) lifo.clone();
Collections.sort(sc);
System.out.println("max=" + sc.get(sc.size() - 1));
}
回答by linski
This code:
这段代码：
public static Integer max(Stack stack) {
if (stack.isEmpty()) {
return Integer.MIN_VALUE;
}
else {
Integer last = (Integer)stack.pop();
Integer next = max(stack);
stack.push(last);
if (last > next) {
return last;
}
else {
return next;
}
}
}
public static void main(String[] args){
Stack lifo = new Stack();
lifo.push(new Integer(4));
lifo.push(new Integer(1));
lifo.push(new Integer(150));
lifo.push(new Integer(40));
lifo.push(new Integer(0));
lifo.push(new Integer(60));
lifo.push(new Integer(47));
lifo.push(new Integer(104));
System.out.println(Arrays.deepToString(lifo.toArray()));
System.out.println(max(lifo));
System.out.println(Arrays.deepToString(lifo.toArray()));
}
outputs:
输出：
[4, 1, 150, 40, 0, 60, 47, 104]
150
[4, 1, 150, 40, 0, 60, 47, 104]
It is a recursion on a given stack, finds the maximum element and doesn't change the stack order.
它是对给定堆栈的递归，查找最大元素并且不更改堆栈顺序。
However iteration is different from recursion only if you define it like that. Also, to find maximum you mustcompare all the elements somehow - in whatever mathematical form, with relational or bitwise operators like Anirudh showed. IMHO, pretty vaguely defined task.
然而，只有当你这样定义它时，迭代才不同于递归。此外，要找到最大值，您必须以某种方式比较所有元素 - 以任何数学形式，使用关系或按位运算符，如 Anirudh所示。恕我直言，相当模糊定义的任务。
回答by Anirudha
You can use bitwise operatorinstead..
您可以改用按位运算符..
public int getMax(int a, int b)
{
int c = a - b;
int k = (c >> 31) & 0x1;
int max = a - k * c;
return max;
}
Now you can do
现在你可以做
int max=Integer.MIN_VALUE-1;
while(!stack.empty())
{
max=getMax(max,stack.pop());
}
回答by Adrian
This can be done in O(1) time and O(n) memory. Modify the push and pop method (or by inheritance extend the standard stack with your own) to keep track of the current max in another stack.
这可以在 O(1) 时间和 O(n) 内存中完成。修改 push 和 pop 方法（或通过继承扩展您自己的标准堆栈）以跟踪另一个堆栈中的当前最大值。
When you push elements onto your stack, push max(currentElem, maxStack.peek()) onto maxStack When you pop elements off the stack, pop the current max from your max stack as well.
当您将元素推入堆栈时，将 max(currentElem, maxStack.peek()) 推入 maxStack 当您从堆栈中弹出元素时，也从最大堆栈中弹出当前最大值。
This solution illustrates it well, so I won't expand more on it: https://stackoverflow.com/a/3435998/1007845
这个解决方案很好地说明了它，所以我不会更多地扩展它：https: //stackoverflow.com/a/3435998/1007845
回答by lc.
Time to think outside of the box. Use the Wolfram Alpha REST API, and ask it to compute the resultof:
是时候跳出框框思考了。使用Wolfram Alpha REST API，并要求它计算以下结果：
"maximum of " + Arrays.deepToString(lifo.toArray())
It will return 150.
它将返回 150。
回答by Peshal
Here is my solution:
这是我的解决方案：
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;
public class StackDemo {
public static void main(String[] args){
Stack lifo = new Stack();
lifo.push(new Integer(4));
lifo.push(new Integer(1));
lifo.push(new Integer(150));
lifo.push(new Integer(40));
lifo.push(new Integer(0));
lifo.push(new Integer(60));
lifo.push(new Integer(47));
lifo.push(new Integer(104));
Object lifoArray[] = lifo.toArray();
Arrays.sort(lifoArray);
System.out.println(lifoArray[lifoArray.length-1]);
}
}
Arrays.sort()arranges in ascending order, so the last value in the sorted array will be the max value.
Arrays.sort()按升序排列，因此排序数组中的最后一个值将是最大值。
回答by sharif2008
1 x -Push the element x into the stack.
1 x - 将元素 x 推入堆栈。
2 -Delete the element present at the top of the stack.
2 - 删除堆栈顶部的元素。
3 -Print the maximum element in the stack.
3 - 打印堆栈中的最大元素。
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Stack <StackItem> st = new Stack <StackItem> ();
int n = sc.nextInt();//number of choice
int choice;
int max = 0;
for (int i = 0; i<n; i++) {
choice = sc.nextInt();
if (choice == 1) {//insert/push an item
int newInt = sc.nextInt();
if (!st.isEmpty()) {
max = st.peek().currentMax;
} else {
max = 0;
}
if (newInt > max) {
max = newInt;
}
StackItem item = new StackItem(newInt, max);
st.push(item);
} else if (choice == 2) {//pop
if (!st.isEmpty()) st.pop();
} else if (choice == 3) {//print the maximum item
System.out.println(st.peek().currentMax);
}
}
}
}
class StackItem {
int val;
int currentMax;
StackItem(int val, int max) {
this.val = val;
this.currentMax = max;
}
}
