如何在不使用max()或迭代它的情况下在堆栈中查找最大整数值？

Question

我在接受采访时被问到以下问题:如果你有一个整数堆栈,你如何在不使用Collections.max的情况下找到堆栈的最大值,而不是迭代堆栈并比较元素.我用下面的代码回答它,因为我不知道使用任何Collections API或迭代Stack并使用比较的另一种方式.有任何想法吗？

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());
        }
    }
}

Answer 1

通过使用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());
}

请注意,自定义Comparator翻转比较,以便Collections.min()实际返回最大值.

Answer 2

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/
    }
} 

Answer 3

不确定这是否满足您的问题需求,但这种方式的使用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));
}

Answer 4

编辑:

没有遍历堆栈

实际上并没有禁止所有迭代.相反,这个问题只是禁止做简单的事情

for (Integer i : lifo)

因此,该解决方案满足了问题的局限性.

只是清空堆栈的副本.弹出副本中的每个元素,始终检查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());

这将在O(n)时间内为您工作,即使您的采访者决定更具限制性并且不允许更多内置功能(最大,最小,排序等).

此外,如果您需要原始安全,但不能使用克隆,您可以使用额外的堆栈:

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());

最后,这假设可以接受与temp变量的比较.如果根本不允许比较,则此解决方案与此方法一起使用.

Answer 5

这段代码:

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()));
}

输出:

[4, 1, 150, 40, 0, 60, 47, 104]
150
[4, 1, 150, 40, 0, 60, 47, 104]

它是给定堆栈的递归,找到最大元素并且不会更改堆栈顺序.

但是,只有在您定义迭代时,迭代才与递归不同.此外,要找到最大值,你必须以某种方式比较所有元素 - 无论以何种数学形式,与Anirudh 表示的关系或按位运算符.恕我直言,相当模糊的任务.

Answer 6

您可以使用按位运算符 ..

public int getMax(int a, int b) 
{
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}

现在你可以做到

int max=Integer.MIN_VALUE-1; 
while(!stack.empty())
{
    max=getMax(max,stack.pop());
}

Answer 7

这可以在O(1)时间和O(n)存储器中完成.修改push和pop方法(或通过继承使用您自己的扩展标准堆栈)来跟踪另一个堆栈中的当前最大值.

将元素推入堆栈时,将max(currentElem,maxStack.peek())推送到maxStack当您从堆栈中弹出元素时,也会从最大堆栈中弹出当前最大值.

这个解决方案很好地说明了,所以我不会对它进行更多扩展:https://stackoverflow.com/a/3435998/1007845