用java编写带堆栈的计算跨度

Question

我正在写一个用堆栈计算跨度的程序 我已经编写了一个代码，下面是我在其中使用的变量：

一个名为X的52个整数数组：这是我们要计算其跨度的数组；在此代码中，X元素将由随机函数初始化

该程序的输出是一个名为S的整数数组，其大小与X相同； S[i]是股票在第i天的跨度

st是一个堆栈

下面是我根据算法编写的代码：

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

下面是我的故事：

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的假设是不正确的。span的定义是“紧靠X[i]之前的连续元素的最大数量X[j]，并且 X[j]≤ X[i]，但该算法似乎在结果中添加了一个。对于{}（没有紧接在前面的较小元素）它是1。对于{}（没有紧接在前面的较小元素）它是1。对于{}（紧接在较小元素前面的1）它是2。对于{}（紧接在较小元素前面的3）它是4

这似乎不符合“最大值”的严格定义，但算法是一致的：如果X[3]应该等于3，那么X[0]和X[1]应该等于零，因为前面没有直接的较小元素

Answer 2

包com。堆叠

公共类股票span{

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