java - 在 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；

这是 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[i] 之前的连续元素 X[j] 的最大数量，这样X[j] ≤ X[i]”，但算法似乎将结果加一。对于 X[0](没有紧接在较小元素之前)它是 1。对于 X[1](没有紧接在较小元素之前)它是 1。对于 X[2](1 紧接在较小元素之前) 是 2。对于 X[3](紧接在较小元素之前的 3)它是 4。

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