Как найти максимальное целочисленное значение в стеке без использования max() или итерации по нему?

Ответ 1

Edit:

без повторения стека

фактически не запрещает всю итерацию. Скорее, вопрос только запрещает делать простые

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) времени, даже если ваши интервьюеры решают быть более ограничительными и не допускать больше встроенных функций (max, min, sort и т.д.).

Кроме того, если вам нужно иметь оригинальное невредимое, но не использовать клон, вы можете сделать это с помощью дополнительного стека:

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

Наконец, это предполагает, что сравнение с временной переменной приемлемо. Если сравнение вообще не допускается, то это решение в сочетании с этим методом будет работать.

Ответ 2

Вместо 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() действительно вернет max.

Ответ 3

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

Ответ 4

Не уверен, что это удовлетворит ваш вопрос, но таким образом можно избежать использования 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));
}

Ответ 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 . IMHO, довольно неопределенная задача.

Ответ 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());
}

Ответ 7

Это можно сделать в O (1) время и O (n) памяти. Измените метод push и pop (или по наследованию расширите стандартный стек с помощью своего собственного), чтобы отслеживать текущий максимум в другом стеке.

Когда вы нажимаете элементы на свой стек, нажмите max (currentElem, maxStack.peek()) на maxStack Когда вы выталкиваете элементы из стека, также выталкивайте текущий максимум из своего максимального стека.

Это решение хорошо иллюстрирует это, поэтому я больше не буду расширять его: fooobar.com/questions/82509/...

Ответ 8

Время думать за пределами коробки. Используйте Wolfram Alpha REST API и попросите его вычислить результат:

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

Он будет вернуть 150.

Ответ 9

Когда вы вставляете элементы в стек, обновите максимальное значение

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

а

   void push(Integer value) {
       //push into stack
       //update max value
   }

Ответ 10

Вы можете преобразовать его в TreeSet с помощью:

int myMax = new TreeSet<Integer>(lifo).last();

Ответ 11

Используйте Collections.sort с компаратором, который сортирует по убыванию, а затем заглядывает верхний элемент из Stack.

Ответ 12

Вот мое решение:

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() упорядочивается в порядке возрастания, поэтому последним значением в отсортированном массиве будет максимальное значение.

Ответ 13

Без итерации вы можете сделать рекурсивный вызов. Если это не домашнее задание, это нелогично. Или, альтернативно, вы можете сделать это без итерации и рекурсии.

Однако быстрый простой способ:

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

}

Ответ 14

1 x -Push элемент 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;
        }
    }