题目
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
思考
1、注意这题是让我们自己去定义一个栈的数据结构
2、那么有LinkedList可以知道我们可以手写一个链表来完成
代码和注释
// 通过手写一个链表来完成
class MinStack {
private Node head;
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
if(head == null){
head = new Node(x,x,null);
}else{
// 每个节点都需要有最小值(不断的用新的head指向老的head，这里要画图理解一下更容易)
head = new Node(x, Math.min(head.min,x),head);
}
}
public void pop() {
head=head.next;
}
public int top() {
return head.val;
}
public int min() {
return head.min;
}
}
public class Node{
// 值
int val;
// 最小值
int min;
// 链表节点
Node next;
public Node(int val, int min,Node next){
this.val = val;
this.min = min;
this.next = next;
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.min();
*/
总结
1、head = new Node(x, Math.min(head.min,x),head);
这段代码比较重要，
- 将最小值置入每个节点中，当我们出栈的时候，就不需要重新计算了
- 新的head不断指向老的head完成栈的结构
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96139.html
