Loading [MathJax]/extensions/AssistiveMML.js

剑指offer30 包含min函数的栈

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.

提示:

  1. 各函数的调用总次数不超过 20000 次

解题思路

方法一:辅助栈

方法二:头插法链表

方法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MinStack {
Node head;

/** initialize your data structure here. */
public MinStack() {

}

public void push(int x) {
if (head == null) {
head = new Node(null, x, x);
} else {
head = new Node(head, x, Math.min(head.min, x));
}
}

public void pop() {
head = head.next;
}

public int top() {
return head.val;
}

public int min() {
return head.min;
}
}

class Node {
Node next;
int val;
int min;

public Node(Node next, int val, int min) {
this.next = next;
this.val = val;
this.min = min;
}
}
Author

John Doe

Posted on

2021-05-28

Updated on

2021-06-13

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.