java - una - tiempo de carga de pilas recargables

¿Cómo encontrar el valor entero máximo en una pila sin usar max() o iterar sobre él?

Question

Me preguntaron en una entrevista la siguiente pregunta: si tiene una pila de enteros, ¿cómo encontraría el valor máximo de la pila sin usar Collections.max y sin iterar sobre la pila y comparar elementos? Respondí con el código a continuación, ya que no conozco otra forma que no sea el uso de ninguna API de colecciones o la iteración sobre la pila y el uso de comparaciones. ¿Algunas ideas?

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

1 x -Pulsa el elemento x en la pila.

2 -Elimina el elemento presente en la parte superior de la pila.

3 -Imprimir el elemento máximo en la pila.

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

Answer 2

Aquí está mi solución:

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() organiza en orden ascendente, por lo que el último valor en la matriz ordenada será el valor máximo.

Answer 3

Cuando inserta elementos en la pila, actualice el valor máximo

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

mientras

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

Answer 4

Este codigo

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

salidas:

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

Es una recursión en una pila dada, encuentra el elemento máximo y no cambia el orden de la pila.

Sin embargo, la iteración es diferente de la recursión solo si la define así . Además, para encontrar el máximo, debe comparar todos los elementos de alguna manera, en cualquier forma matemática, con operadores relacionales o bitwise como lo showed Anirudh. En mi humilde opinión, tarea bastante vagamente definida.

Answer 5

Esto se puede hacer en tiempo O (1) y en memoria O (n). Modifique el método push y pop (o, por herencia, extienda la pila estándar con la suya propia) para realizar un seguimiento del máximo actual en otra pila.

Cuando coloca elementos en su pila, presione max (currentElem, maxStack.peek ()) en maxStack Cuando saque elementos de la pila, también extraiga el máximo actual de su pila máxima.

Esta solución lo ilustra bien, por lo que no me extenderé más: https://.com/a/3435998/1007845

Answer 6

No estoy seguro de que esto satisfaga la necesidad de su pregunta, pero de esta manera el uso de max() y la iteration podrían evitarse, de todos modos la sort usa la iteration y Comparable en segundo plano.

if (!lifo.isEmpty()) {
    Stack sc = (Stack) lifo.clone();
    Collections.sort(sc);
    System.out.println("max=" + sc.get(sc.size() - 1));
}

Answer 7

Puede utilizar el operador bitwise en su lugar ...

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

Ahora puedes hacer

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

Answer 8

Puedes convertirlo en un TreeSet con:

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

Answer 9

Sin iteración puedes hacer una llamada recursiva. Si no es tarea, no es lógico hacerlo. O, alternativamente, puede hacer esto sin iteración y recursión.

Sin embargo, un enfoque rápido y simple está aquí:

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

}

Answer 10

Tiempo para pensar fuera de la caja. Use la API REST de Wolfram Alpha y pídale que calcule el resultado de:

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

Volverá 150 .

Answer 11

Usando Collections.min() lugar:

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

Tenga en cuenta que el Comparator personalizado invierte la comparación para que Collections.min() devuelva el máximo.

Answer 12

Use Collections.sort con un Comparator que ordene en orden descendente y luego eche un vistazo al elemento superior de la Pila.

Answer 13

Editar:

sin iterar sobre la pila

en realidad no prohíbe toda iteración. Más bien, la pregunta solo prohíbe hacer lo simple.

for (Integer i : lifo)

Por lo tanto, esta solución satisface las limitaciones de la pregunta.

Simplemente vacía una copia de la pila. extraiga cada uno de los elementos de la copia, verificando el máximo contra un entero todo el tiempo.

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

Esto funcionará para usted en un tiempo O (n) incluso si sus entrevistadores deciden ser más restrictivos y no permiten más funciones integradas (máx, mín, clasificación, etc.).

Además, si necesita que el original no esté dañado, pero no puede usar el clon, puede hacerlo con una pila adicional:

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

Finalmente, esto supone que la comparación con una variable temporal es aceptable. Si no se permite ninguna comparación, entonces esta solución junto con este método funcionará.

Answer 14

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