题目
- 概述：设计一个栈，除了支持栈的核心操作push(x)，pop()，top()外，还支持在常数时间内找到栈中最小的元素
- push(x)：将x入栈
- pop()：将栈顶元素出栈
- top()：获取栈顶元素
- getMin()：取得栈中最小元素
出处：https://leetcode-cn.com/problems/min-stack/
思路
为栈中每一个结点添加一个属性minValue，标志以该结点为栈顶的栈的最小元素
每次入栈的结点的minValue为该结点的值本身
入栈时比较入栈的结点和栈顶结点的minValue，若入栈的结点的minValue大于栈顶结点的minValue，则更新入栈的结点的minValue为栈顶结点的minValue
注意：如果栈中没有元素，则直接入栈即可
- 栈中最小元素为栈顶元素的minValue
代码
class MinStack {
private Node dummyHead;
/** initialize your data structure here. */
public MinStack() {
dummyHead = new Node(0);
}
public void push(int x) {
Node newNode = new Node(x);
if (dummyHead.next != null) {
if (newNode.minValue > getMin()) {
newNode.minValue = getMin();
}
}
newNode.next = dummyHead.next;
dummyHead.next = newNode;
}
public void pop() {
Node delNode = dummyHead.next;
dummyHead.next = delNode.next;
delNode.next = null;
delNode = null;
}
public int top() {
return dummyHead.next.value;
}
public int getMin() {
return dummyHead.next.minValue;
}
class Node {
int value;
Node next;
int minValue;
public Node(int value) {
this.value = value;
this.next = null;
this.minValue = value;
}
}
}
