JAVA数据结构-比较难的栈算法问题

Question

1.实现类似栈的数据结构（数据类型可以只为Integer），包含push(),pop(),findMin()3个方法，其中findMin()是输出当前数据结构中最小元素的值。
注意：所有的方法时间复杂度必须为O（1）！！！即不能使用循环遍历的方法找出最小值！！！2.使用1个数组实现3个栈。当且仅当数组被全部填满时，才能抛出栈溢出异常。也就是说，数组有空间时，可以支持任意栈的push()操作。第1个问题我已经解决了，欢迎大家来探讨，看看有没有更好的解法。我是用伴随矩阵做的。
第2个问题实在不会，求大牛解决。有木有？

Answer 1

有没有更好的办法，移动数组元素需要O（N），可不可以用O(1)实现

Answer 2

唉，还是自己解决问题了，下面上代码。1.实现类似栈的数据结构（数据类型可以只为Integer），包含push(),pop(),findMin()3个方法，其中findMin()是输出当前数据结构中最小元素的值。/*
 * 实现一个数据结构，包括push,pop,findMin方法，所有方法的时间复杂度均为O(1)
 */
public class MyStack {
private static final int SIZE = 100;
private int[] data = new int[SIZE];
private int topOfArray = -1;
private int topOfMinData = -1;
private int size = 0;
private int min;
private int[] minData = new int[SIZE];

public MyStack(){
clear();
}

public void clear(){
data = new int[SIZE];
minData = new int[SIZE];
topOfArray = -1;
size = 0;
}

public void push(int x){
data[++topOfArray] = x;
size++;
if(topOfArray == 0 || data[topOfArray] <= min){
min = data[topOfArray];
minData[++topOfMinData] = data[topOfArray];
}
}

public int pop(){
size--;
if(data[topOfArray] == min && topOfArray > 0){
min = minData[--topOfMinData];
}
else if(topOfArray == 0){
clear();
return 0;
}
return data[topOfArray--];
}

public int findMin(){
if(topOfArray == -1){
return Integer.MAX_VALUE * (-1);
}
return minData[topOfMinData];
}

}public class Test {
public static void main(String[] args) {
MyStack myStack = new MyStack();
myStack.push(2);
myStack.push(3);
myStack.push(6);
myStack.push(0);
myStack.push(-1);
myStack.push(0);
myStack.push(1);
System.out.println("The min is " + myStack.findMin());
myStack.pop();
myStack.pop();
myStack.pop();
myStack.pop();
System.out.println("The min is " + myStack.findMin());
}
}Result:
The min is -1
The min is 2
2.使用1个数组实现3个栈。当且仅当数组被全部填满时，才能抛出栈溢出异常。也就是说，数组有空间时，可以支持任意栈的push()操作。
/**使用1个数组实现3个栈。当且仅当数组被全部填满时，才能抛出栈溢出异常。也就是说，数组有空间时，可以支持任意栈的push()操作
 * push(),pop()方法均为O(1) 
 */public class MyStack {
private static final int SIZE = 10;
private static int[] data = new int[SIZE];
private int[] index = new int[SIZE];
private static int topOfArray = -1;
private int topIndex = -1;
private static int[] unUsedIndex = new int[SIZE];


public int getTopIndex() {
return topIndex;
} private static int size = 0; public MyStack() {
clear();
} public void clear() {
data = new int[SIZE];
index = new int[SIZE];
topOfArray = -1;
size = 0;
for(int i = 0;i < SIZE;i++){
unUsedIndex[i] = i;
}
} public void push(int x) {
data[unUsedIndex[++topOfArray]] = x;
index[++topIndex] = unUsedIndex[topOfArray];
size++;
} public int pop() {
size--;
unUsedIndex[topOfArray--] = index[topIndex];
return data[index[topIndex--]];
} public static void totalStackprint(){
System.out.print("当前数组中元素:");
for(int i = 0;i < size;i++){
System.out.print(data[i] + " ");
}
System.out.println();
}

public void print(){
System.out.print("当前栈中元素:");
for(int i = 0;i <= topIndex;i++){
System.out.print(data[index[i]] + " ");
}
System.out.println();
}

public int size(){
return size;
}

}
public class Test {
static MyStack myStack1 = new MyStack();
static MyStack myStack2 = new MyStack();
static MyStack myStack3 = new MyStack();

public static void main(String[] argc) {
pushData1();
popData();
pushData2();
}

static void pushData1(){
myStack1.push(-2);
myStack2.push(3);
myStack3.push(1);
myStack2.push(2);
myStack1.push(6);
myStack2.push(-4);
myStack2.push(5);
myStack1.push(6);
myStack2.push(2);
myStack2.push(2);
MyStack.totalStackprint();
print();
}

static void popData(){
System.out.print("移除myStack2中所有元素");
while(myStack2.getTopIndex() >= 0){
System.out.print(myStack2.pop() + " ");
}
System.out.println();
print();
}

static void pushData2(){
myStack3.push(-6);
myStack1.push(24);
myStack2.push(15);
myStack2.push(33);
myStack1.push(12);
myStack3.push(-9);
MyStack.totalStackprint();
print();
}

static void print(){
myStack1.print();
myStack2.print();
myStack3.print();
}
}Result:当前数组中元素:-2 3 1 2 6 -4 5 6 2 2 
当前栈中元素:-2 6 6 
当前栈中元素:3 2 -4 5 2 2 
当前栈中元素:1 
移除myStack2中所有元素2 2 5 -4 2 3 
当前栈中元素:-2 6 6 
当前栈中元素:
当前栈中元素:1 
当前数组中元素:-2 -6 1 24 6 15 33 6 12 -9 
当前栈中元素:-2 6 6 24 12 
当前栈中元素:15 33 
当前栈中元素:1 -6 -9 

Answer 3

问题2
你用了三个数组来实现，窃以为与题意不合。
本题并未要求时间复杂度，应该是考察合理利用空间的能力。
如果能用3个数组，直接用3个数组代表三个栈就好了。我觉得最好的方法应该是这样：
假设数组长度为n
栈1从数组下标0开始逐渐递增下标，栈2把顺序反过来，从下标n-1开始逐渐递减下标，这样这两个栈的元素永远不需要被移动。
栈3从数组下标n/3开始，根据需要栈3可能需要被移动。

Answer 4

不是哦，我的那个数组存放的是最小值的序列。
不能存放当前最小值，因为在pop()弹出最小值的时候，需要重新遍历数组找当前的最小值。那么时间复杂度上升为O(N),不符合题意O(1)。
如：2，-1，3，-2 //可以保存-2
但是当-2被弹出时，剩下2,-1，3，那么就要遍历了。

Answer 5

LZ回答你的就是这个啊比如按你说的 -1 0 2 -1
pop的时候-1弹出，你怎么去找下一个最小值呢？

Answer 6

你说的对，我没有考虑到pop()

Answer 7

我没去找最小值啊，在push的时候生成了最小元素的子序列，存放在一个数组中。
如：2,-1,0,1,3,2,-2,1,-2
数组依次存放2,-1,0,-2,-2
在pop的时候，如果弹出元素和最小子序列数组最大下标所在元素相等，最小子序列数组长度-1
如pop -2,1,-2,
数组为2,-1,0,-2
2,-1,0,-2
2,-1,0
此时最小值为0，不需要遍历

Answer 8

可能是我的描述有点问题。
题目的意思是必须将所有栈的元素存放在同一个数组中，但是可以指定栈元素对应的数组元素下标（存放在数组或者是其他数据结构中），否则没法对指定栈进行push,pop操作。

Answer 9

哈哈，第一题我给个取巧的方法。。局限性大，不过也应该符合题意了，现在的代码最大的数组只能取到16，看下谁能完善吧。
public class Test7 {
public static void main(String[] args) {
Stacks st = new Stacks();

}
} class Stacks {
int[] a;
int num = 0;
int min = 0;
int num2 = 0;
long l = 0;
int num3 = 0;
public Stacks() {
a = new int[16];
}

public void push(Integer i) {
a[num] = i;
if(num==0) {
min = a[num];
num2 = num2^min;
l = l|num;
}
else if(a[num]<min) {
min = a[num];
num2 = num2^min;
if(num>=10) {
num3 = 1;
int tmp = num%10;
l = (l<<4)+tmp;
}
else l = (l<<4)+num;
}

num++;
}

public Integer pop() {
Integer inte = null;
if(a[num-1]==min&&num3==0) {
num2 = num2^min;
inte = a[num-1];
a[num-1] = 0;
num--;
l = l >>>4;
long temp = (l>>>4)<<4;
int mins = (int)(l^temp);
min = a[mins];
}
else if(a[num-1]==min&&num3==1) {
num2 = num2^min;
inte = a[num-1];
a[num-1] = 0;
num--;
l = l >>>4;
long temp = (l>>>4)<<4;
int mins = (int)(l^temp)+10;
min = a[mins];
if(num<10) {
num3 = 0;
}
}
else {
inte = a[num-1];
a[num-1] = 0;
num--;
}
return inte;
}

public Integer findMin() {
int out = num2^min;
out = num2^out;
return out;
}
}

Answer 10

给个效果大家看下public static void main(String[] args) {
Stacks st = new Stacks();
st.push(2);
st.push(8);
st.push(3);
st.push(-5);
System.out.println("移除前最少值："+st.findMin()+"  移除后的返回值和最少值："+st.pop()+"　"+st.findMin());
System.out.println("移除前最少值："+st.findMin()+"  移除后的返回值和最少值："+st.pop()+"　"+st.findMin());
System.out.println("移除前最少值："+st.findMin()+"  移除后的返回值和最少值："+st.pop()+"　"+st.findMin());
}移除前最少值：-5  移除后的返回值和最少值：-5　2
移除前最少值：2  移除后的返回值和最少值：3　2
移除前最少值：2  移除后的返回值和最少值：8　2

Answer 11

问题2可以考虑每个stack有个id和topIndex和size和flag表示已满，操作一个static的int[]，每次push或pop的时候，通过id,toIndex,size,flag来计算实际int[]的下标
比如第1个stack，id是1，每次push，pop取数组下标 0, 3, 6,... 即topIndex=id-1,topIndex+=3 
第2个stack，id是2,每次push，pop取数组下标1, 4, 7,...
第3个stack，id是3,每次2,5,8,...
id可以通过一个private static int count = 0;每次new的时候count++，id=count
当自身的数组下标满的时候，改变flag现在有个大概思路了，不过下班了，明天有空再看

Answer 12

这个方法可能不合题意，假设数组长度为10，那么3个栈可以分别存储a,b,c个元素，只要满足a+b+c =10就可以

Answer 13

如果把最小值pop出来，剩下的元素怎么求用O(1)求最小值？

Answer 14

我的方法就是用1个值记录下来，pop后一样可以一步找出下一个最少值的位置啊