思路
维护最小值栈
建立兄弟栈
在push新元素的时候 对新元素和旧元素比较大小
小 就入栈新元素 反之入栈 peek(旧元素)
出栈时 兄弟栈也依次出栈即可

优化
空间换时间
没有更小的就不加入到兄弟栈
在push新元素的时候 对新元素和旧元素比较大小 然后入栈即可
pop时 在兄弟栈对比是否相同 再pop
代码
package _09_Linear.Stack_QueuePractice;
import _09_Linear.Stack.IStack;
import _09_Linear.Stack.MyStack;
import _09_Linear.list.DoubleLinkList;
import _09_Linear.list.ListNode;
import org.junit.Test;
import java.util.EmptyStackException;
public class StackWithMin<T> extends DoubleLinkList<T> implements IStack<T> {
@Test
public void test()throws Exception {
StackWithMin stack = new StackWithMin<>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(-5);
stack.push(5);
System.out.println(stack.min_O1());
// System.out.println(stack.min_On());
stack.pop();
stack.pop();
System.out.println(stack.min_O1());
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack.min_O1());
}
@Override
public void push(T e) {
add(e);
//维护最小值栈 当然还可以节约空间 减少重复
if (brother.empty()) {
brother.push(e);
} else {
T peek = brother.peek();
if ((Integer) e < (Integer) peek) {
brother.push(e);
} else {
brother.push(peek);
}
}
}
@Override
public T pop() {
if (size <= 0) throw new EmptyStackException();
ListNode<T> the = super.last.getPre();//last 的前一个
T res = the.getData();
the.getPre().setNext(last);//目标元素的前一个 指向最后
last.setPre(the.getPre());//最后一个元素指向目标元素的前一个
the.setPre(null);
the.setNext(null);
size--;
brother.pop();//兄弟也弹出
return res;
}
/**
* O(n) 遍历
*
* @return
*/
public int min_On() {
ListNode<T> h = first.getNext();
int min = -1;
while (h != last) {
if ((Integer) h.getData() <= min) {
min = (Integer) h.getData();
}
h = h.getNext();//后移
}
return min;
}
/**
* O(1) 空间换时间
* 再Push时 维护最小值栈
* @return
* @throws Exception
*/
//维护栈
private MyStack<T> brother = new MyStack();
public int min_O1() throws Exception {
if (!brother.empty())
return (Integer) brother.peek();
else
throw new Exception("没有元素了 所以无最小值");
}
//----------------------------------------
@Override
public boolean empty() {
return size == 0;
}
@Override
public int getSize() {
return size;
}
@Override
public T peek() {
return last.getPre().getData();
}
}
本文作者:Author: 寒光博客
文章标题:[java]Stack 设计一个带最小值的栈 建立维护栈
本文地址:https://dxoca.cn/java/305.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/java/305.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。