help implementing All Nearest Smaller Values algorithm
Posted
by davit-datuashvili
on Stack Overflow
See other posts from Stack Overflow
or by davit-datuashvili
Published on 2010-05-14T21:28:09Z
Indexed on
2010/05/14
21:54 UTC
Read the original article
Hit count: 201
http://en.wikipedia.org/wiki/All_nearest_smaller_values this is site of the problem and here is my code but i have some trouble to implement it
import java.util.*;
public class stack{
public static void main(String[]args){
int x[]=new int[]{ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
Stack<Integer> st=new Stack<Integer>();
for (int a:x){
while (!st.empty() && st.pop()>=a){
System.out.println( st.pop());
if (st.empty()){
break;
}
else{
st.push(a);
}
}
}
}
}
and here is pseudo code from site
S = new empty stack data structure
for x in the input sequence:
while S is nonempty and the top element of S is greater than or equal to x:
pop S
if S is empty:
x has no preceding smaller value
else:
the nearest smaller value to x is the top element of S
push x onto S
© Stack Overflow or respective owner