schreiben Compute Spanne mit Stapeln in Java

Question

ich für Computing mit Stapeln ein Programm schreibe ich habe einen Code geschrieben und hier sind die Variable I in sie verwendet haben:

Ein Array von 52 ganzen Zahlen genannt X: Diese ist das Array, das wir seine Spannen berechnen möchten; In diesem Code werden X Elemente durch Zufallsfunktion initialisiert;

Die Ausgabe dieses Programms ist ein Integer-Array namens S, das in der gleichen Größe wie X ist; und S [i] ist die Spannweite der Aktie am Tag i

st ist ein Stapel.

hier So ist der Code, den ich auf der Grundlage des Algorithmus geschrieben haben:

public class ComputingSpansInStack { 

static int [] X = new int[52]; 
static int [] S = new int[52]; 
public static void SetX() 
{ 

    Random rn = new Random(); 
    for (int i = 0; i < 52; i++) { 
     X[i] = 1 + rn.nextInt(100); 
    } 
} 

public static void main(String[] args) { 
    SetX(); 
    int h; 
    Stack<Integer> st=new MyStack<>(); 
    boolean done; 
    for (int i = 0; i<52 ; i++) 
    { 
     done = false; 

     while(!(st.isEmpty()||done)) 
       { 
        if(X[i]>= X[st.top()]) 
         st.pop(); 
        else 
         done = true; 
       } 
     if(st.isEmpty()) 
      h = -1; 
     else 
      h = st.top(); 

     S[i] = i - h; 
     st.push(i); 
    } 


    for (int i =0; i<52; i++) 
    { 
     System.out.println(X[i] + " "+ S[i]); 
    } 
} 

aber die Ausgabe ist hier:

38 --- 1

7 --- --- 1

16 ----- 2

62 ------ 4

35 ----- 1

31 ----- 1

6 ----- 1 .......

Problem: für 62 Es sollte 3 nicht 4;

hier ist MyStack:

public class MyStack<E> implements Stack<E>{ 
private final E s[]; 
int t=0; 


public MyStack() { 
    this.s = (E[]) new Object[100]; 
} 


public int size(){ 
    return t; 
} 


public boolean isEmpty(){ 
    switch(size()){ 
     case 0: 
      return true; 
    } 
    return false; 
} 


public E top() { 
    if(isEmpty()) 
     throw new EmptyStackException(); 
    return s[t-1]; 
} 

public void push(E element) { 
    if(isEmpty()) 
     s[0]= element; 
    else 
     s[t]= element; 
    t++; 
} 


public E pop() { 
      E x; 
    if(isEmpty()) 
     throw new EmptyStackException(); 
    else{ 
     x = s[t-1]; 
     s[t-1] = null; 
     t--; 
    } 
    return x; 
} 

}

jede Hilfe ??

Vielen Dank im Voraus

Answer 1

Ihre Implementierung ist korrekt. S[i] = i + 1, wobei X[i] größer als alle vorhergehenden Elemente ist, so da X[3] (64) größer ist als alle vorhergehenden Elemente, S[3] = (3 + 1) = 4.

Mit anderen Worten: Ihre Annahme, dass S[3] sollte gleich 3 ist falsch. Die Definition eines Bereichs ist "die maximale Anzahl aufeinanderfolgender Elemente X[j] unmittelbar vorhergehend X[i] und so dass X[j] ≤ X[i]", aber der Algorithmus scheint eins zum Ergebnis hinzuzufügen. Für X[0] (keine unmittelbar vorhergehenden kleineren Elemente) ist es 1. Für X[1] (keine unmittelbar vorangehenden kleineren Elemente) ist es 1. Für X[2] (1 unmittelbar vorangestelltes kleineres Element) ist es 2. Für X[3] (3 unmittelbar vorangehende kleinere Elemente) ist es 4.

Dies scheint nicht die strenge Definition des "Maximum" zu erfüllen, aber der Algorithmus ist konsistent: Wenn X[3] gleich 3 sein sollte, dann X [0] und X [1] sollte gleich Null sein, da dort sind keine unmittelbar vorangehenden kleineren Elemente.

Answer 2

paket com.Stapel;

public class StockSpan {

private int arr[] = { 10, 4, 5, 90, 120, 80 }; 

public void getSpan() { 
    StackImpl s = new StackImpl<Integer>(); 
    s.push(0); 
    int stockSpanRes[] = new int[arr.length]; 
    stockSpanRes[0] = 1; 
    for (int i = 0; i < arr.length; i++) { 
     while (!s.isEmpty() && arr[(int) s.peek()] <= arr[i]) { 
      s.pop(); 
     } 
     stockSpanRes[i] = s.isEmpty() ? i + 1 : i - (int) s.peek(); 
     s.push(i); 
    } 

    for (int i = 0; i < arr.length; i++) { 
     System.out.println(stockSpanRes[i]); 
    } 
} 

public static void main(String[] args) { 
    StockSpan s = new StockSpan(); 
    s.getSpan(); 

} 

}

Einzelheiten besuchen https://github.com/ranjeetsinha13/androidcodes/tree/master/DS_Algos/src/com/stacks