18

我在一次采访中被问到以下问题：如果你有一个整数堆栈，你如何在不使用 Collections.max 并且不迭代堆栈和比较元素的情况下找到堆栈的最大值。我用下面的代码回答了这个问题，因为我不知道除了使用任何 Collections 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());
        }
    }
}
4

14 回答 14

31

通过使用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()实际返回最大值。

于 2013-07-24T18:09:24.143 回答
11 
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/
    }
}
于 2013-07-24T19:40:01.830 回答
10

编辑：

无需遍历堆栈

实际上并不禁止所有迭代。相反，这个问题只禁止做简单的

for (Integer i : lifo)

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

只需清空堆栈的副本。从副本中弹出每个元素，一直检查最大值是否为整数。

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

最后，这假设与临时变量的比较是可以接受的。如果根本不允许比较，则此解决方案与此方法结合将起作用。

于 2013-07-24T18:05:17.313 回答
10

不确定这是否会满足您的问题需求，但这种方式可以避免使用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));
}
于 2013-07-24T18:15:51.780 回答
7

这段代码：

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所示。恕我直言，定义非常模糊的任务。

于 2013-07-24T18:41:37.310 回答
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());
}
于 2013-07-24T18:22:26.957 回答
5

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

当您将元素压入堆栈时，将 max(currentElem, maxStack.peek()) 压入 maxStack 当您将元素从堆栈中弹出时，也将当前最大值从您的最大堆栈中弹出。

该解决方案很好地说明了这一点，因此我不会对其进行更多扩展：https ://stackoverflow.com/a/3435998/1007845

于 2013-07-24T18:24:08.360 回答
4

是时候跳出框框思考了。使用Wolfram Alpha REST API并要求它计算以下结果：

"maximum of " + Arrays.deepToString(lifo.toArray())

它将返回 150。

于 2013-07-24T18:52:55.337 回答
1

这是我的解决方案：

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()以升序排列，因此排序数组中的最后一个值将是最大值。

于 2013-07-24T22:50:11.660 回答
1

将元素压入堆栈时，更新最大值

void main()
    int max = Integer.min
    lifo.push(1)

尽管

   void push(Integer value) {
       //push into stack
       //update max value
   }
于 2013-07-24T18:06:13.753 回答
1

您可以将其转换为TreeSet：

int myMax = new TreeSet<Integer>(lifo).last();
于 2013-07-24T18:07:34.790 回答
1

将 Collections.sort 与按降序排序的 Comparator 一起使用，然后从 Stack 中查看顶部元素。

于 2013-07-24T18:07:51.477 回答
1

1 x - 将元素 x 推入堆栈。

2 - 删除存在于堆栈顶部的元素。

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;
        }
    }
于 2017-01-16T20:56:27.713 回答
0

如果没有迭代，您可以进行递归调用。如果这不是家庭作业，那么这样做是不合逻辑的。或者，您可以在没有迭代和递归的情况下执行此操作。

然而，这里有一个快速简单的方法：

public class StackDemo {
    public static int max = 0; //set this to least, may be negative
    public static Stack lifo = new Stack();
    public static void main(String[] args){        
        pushToStack(new Integer(4));
        pushToStack(new Integer(1));

        if(!lifo.isEmpty()){
            Object max = Collections.max(lifo);
            System.out.println("max=" + max);
        }
    }
    void static int pushToStack(Integer value){
        lifo.push(value);
        if(max<value){
        max = value;
        }
        return max;
    }    

}
于 2013-07-24T18:10:39.993 回答