बारे में जावा में ढेर साथ कंप्यूट अवधि

Question

मैं कंप्यूटिंग ढेर साथ फैला मैं एक कोड लिखा और यहाँ चर मैं इसे में प्रयोग किया जाता है है के लिए एक कार्यक्रम लिख रहा हूँ:

52 नामित एक्स पूर्णांकों की एक सरणी: इस वह सरणी है जिसे हम अपने स्पैन की गणना करना चाहते हैं; इस कोड में एक्स तत्वों को यादृच्छिक फ़ंक्शन द्वारा प्रारंभ किया जाएगा;

इस कार्यक्रम का आउटपुट एक पूर्णांक एरे नामित एस है जो एक्स के समान आकार में है; और एस [i] दिन

सेंट पर स्टॉक का विस्तार है।

तो यहाँ कोड है कि मैं एल्गोरिथ्म के आधार पर लिखा है है:

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

लेकिन उत्पादन यहाँ है:

38 --- 1

7 --- --- 1

16 ----- 2

62 ------ 4

35 ----- 1

31 ----- 1

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

समस्या: 62 के लिए यह 3 नहीं 4 होना चाहिए;

यहाँ

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

}

कोई मदद ??

अग्रिम धन्यवाद

Answer 1

आपका कार्यान्वयन सही है। S[i] = i + 1 जहां X[i] सभी पूर्ववर्ती तत्वों से अधिक है, तो के बाद से X[3] (64), S[3] = (3 + 1) = 4.

दूसरे शब्दों में, अपने धारणा सभी पूर्ववर्ती तत्वों से अधिक होता है कि S[3] बराबर 3 होना चाहिए गलत है। एक अवधि की परिभाषा "लगातार X[j] की अधिकतम संख्या X[i] से पहले की संख्या और X[j] ≤ X[i]" है, लेकिन एल्गोरिदम परिणाम में एक जोड़ना प्रतीत होता है। X[0] (तुरंत छोटे तत्वों से पहले नहीं) के लिए यह 1 है। X[1] (तुरंत छोटे तत्वों से पहले नहीं) यह 1 है। X[2] (1 तत्व के तुरंत बाद 1) यह 2 है। X[3] (3 छोटे तत्वों से पहले तुरंत) 4.

यह "अधिकतम" की सख्त परिभाषा को पूरा नहीं करता है, लेकिन एल्गोरिदम सुसंगत है: यदि X[3] बराबर 3 होना चाहिए, तो एक्स [0] और एक्स [1] शून्य के बराबर होना चाहिए, क्योंकि वहां से छोटे तत्वों से पहले तुरंत नहीं हैं।

Answer 2

पैकेज कॉम।ढेर;

सार्वजनिक वर्ग 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(); 

} 

}

विवरण के लिए, https://github.com/ranjeetsinha13/androidcodes/tree/master/DS_Algos/src/com/stacks