用java编写带堆栈的计算跨度
我正在写一个用堆栈计算跨度的程序 我已经编写了一个代码,下面是我在其中使用的变量:
一个名为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;
}
}
有什么帮助吗
提前谢谢
# 1 楼答案
您的实现是正确的
S[i]
=i+1,其中X[i]
大于所有前面的元素,因此由于X[3]
(64)大于所有前面的元素,S[3]
=(3+1)=4换句话说,你认为}(没有紧接在前面的较小元素)它是1。对于{}(没有紧接在前面的较小元素)它是1。对于{}(紧接在较小元素前面的1)它是2。对于{}(紧接在较小元素前面的3)它是4
S[3]
应该等于3的假设是不正确的。span的定义是“紧靠X[i]
之前的连续元素的最大数量X[j]
,并且X[j]
≤X[i]
,但该算法似乎在结果中添加了一个。对于{这似乎不符合“最大值”的严格定义,但算法是一致的:如果
X[3]
应该等于3,那么X[0]和X[1]应该等于零,因为前面没有直接的较小元素# 2 楼答案
包com。堆叠
公共类股票span{
}
详情请浏览https://github.com/ranjeetsinha13/androidcodes/tree/master/DS_Algos/src/com/stacks