链接
https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
难度： #简单
题目
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
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 次
代码框架
class MinStack {
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
}
public void pop() {
}
public int top() {
}
public int min() {
}
}
/**
* 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();
*/
题目解析
该题的难度主要在于调用 min、push 及 pop 的时间复杂度都是 O(1)，
使用栈或者链表都可以保证push和pop的时间复杂度是O(1),
只要另外找个一个解答思路，
保证min的时间复杂度是O(1)即可。
另外解释一下题目中的几个函数，
push元素入栈，
pop元素出栈，但没有返回值，
top查看栈顶元素，
min返回当前最小的元素。
解答思路1：
用Stack来进行堆栈操作，用TreeSet来找到最小值,注意同时记录重复出现的数据。
解答思路2：
使用两个栈，主栈用于正常的入栈和出栈操作，
辅助栈用于记录当前的最小值，注意这个栈中的最小值是和主栈对应的，
主栈的元素入栈和出栈时，这个最小值是变化的。
解答思路3：
使用一个栈，栈中保存的不仅仅是Integer，
而是一个封装的节点对象，
该节点保存当前的元素，以及当前的最小值。
解答思路4：
使用一个栈，这个栈是用LinkedList模拟出来的，
为了符合题意，限制性的只能使用其四个方法，
分别为isEmpty();addLast();getLast();removeLast();
栈中保存的不仅仅是Integer，
而是一个封装的节点对象，
该节点保存当前的元素，以及当前的最小值。
解答思路5：
自己实现单向链表来模拟一个栈，
对元素的入栈和出栈操作都在链表头部即可。
栈中保存的不仅仅是Integer，
而是一个封装的节点对象，
该节点保存当前的元素，以及当前的最小值,
还有指向下一个节点的指针。
感觉该解题思路是最符合题意的，
特别是可以清楚的看出时间复杂度，
确保调用 min、push 及 pop 的时间复杂度都是 O(1)，
同时空间复杂度为O(n)。
测试用例
package edu.yuwen.sowrd.num30.solution;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import edu.yuwen.sowrd.num30.sol5.MinStack;
public class MinStackTest {
@Test
public void testCase1() {
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
int res = minStack.min(); // 返回 -3.
Assertions.assertEquals(-3, res);
minStack.pop();
res = minStack.top(); // 返回 0.
Assertions.assertEquals(0, res);
res = minStack.min(); // 返回 -2.
Assertions.assertEquals(-2, res);
}
@Test
public void testCase2() {
MinStack minStack = new MinStack();
minStack.push(0);
minStack.push(1);
minStack.push(0);
int res = minStack.min(); // 返回 0.
Assertions.assertEquals(0, res);
minStack.pop();
res = minStack.min(); // 返回 0.
Assertions.assertEquals(0, res);
}
@Test
public void testCase3() {
MinStack minStack = new MinStack();
minStack.push(2);
minStack.push(0);
minStack.push(3);
minStack.push(0);
int res = minStack.min(); // 返回 0.
Assertions.assertEquals(0, res);
minStack.pop();
res = minStack.min(); // 返回 0.
Assertions.assertEquals(0, res);
minStack.pop();
res = minStack.min(); // 返回 0.
Assertions.assertEquals(0, res);
minStack.pop();
res = minStack.min(); // 返回 2.
Assertions.assertEquals(2, res);
}
}
解答1
package edu.yuwen.sowrd.num30.sol1;
import java.util.Stack;
import java.util.TreeMap;
public class MinStack {
// 用Stack来进行堆栈操作
Stack<Integer> stack;
// 用TreeSet来找到最小值,同时记录重复数据
TreeMap<Integer, Integer> treeMap;
public MinStack() {
stack = new Stack<>();
treeMap = new TreeMap<>();
}
public void push(int x) {
stack.push(x);
Integer value = treeMap.get(x);
if (value == null) {
value = 1;
} else {
value++;
}
treeMap.put(x, value);
}
// 弹出栈顶元素
public void pop() {
int num = stack.pop();
Integer value = treeMap.get(num);
value--;
if (value == 0) {
treeMap.remove(num);
} else {
treeMap.put(num, value);
}
}
// 查看栈顶元素
public int top() {
return stack.peek();
}
public int min() {
return treeMap.firstKey();
}
}
解答2
package edu.yuwen.sowrd.num30.sol2;
import java.util.Stack;
public class MinStack {
// 主栈和辅助栈
Stack<Integer> master;
Stack<Integer> slave;
public MinStack() {
master = new Stack<>();
slave = new Stack<>();
}
public void push(int x) {
master.push(x);
// 如果辅助栈为空，则当前元素就是最小值
if (slave.isEmpty()) {
slave.push(x);
}
// 否则和slave栈顶的最小值比较
else {
Integer min = slave.peek();
// 如果x小于最小值min则插入x，否则插入min
if (x < min) {
slave.push(x);
} else {
slave.push(min);
}
}
}
public void pop() {
master.pop();
slave.pop();
}
public int top() {
return master.peek();
}
public int min() {
return slave.peek();
}
}
解答3
package edu.yuwen.sowrd.num30.sol3;
import java.util.Stack;
public class MinStack {
Stack<Node> stack;
public MinStack() {
stack = new Stack<>();
}
public void push(int x) {
Integer min = null;
// 堆栈为空，当前元素就是最小值
if (stack.isEmpty()) {
min = x;
}
// 否则取出上一个节点的最小值进行比较
else {
Node pre = stack.peek();
min = pre.min;
// 如果当前元素小于最小值min，则更新min的值
if (x < min) {
min = x;
}
}
Node item = new Node(x, min);
stack.push(item);
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek().value;
}
public int min() {
return stack.peek().min;
}
}
class Node {
// 当前元素
Integer value;
// 当前最小值
Integer min;
Node(Integer value, Integer min) {
this.value = value;
this.min = min;
}
}
解答4
package edu.yuwen.sowrd.num30.sol4;
import java.util.LinkedList;
public class MinStack {
LinkedList<Node> stack;
public MinStack() {
stack = new LinkedList<>();
}
public void push(int x) {
Integer min = null;
// 堆栈为空，当前元素就是最小值
if (stack.isEmpty()) {
min = x;
}
// 否则取出上一个节点的最小值进行比较
else {
Node pre = stack.getLast();
min = pre.min;
// 如果当前元素小于最小值min，则更新min的值
if (x < min) {
min = x;
}
}
Node item = new Node(x, min);
stack.addLast(item);
}
public void pop() {
stack.removeLast();
}
public int top() {
return stack.getLast().value;
}
public int min() {
return stack.getLast().min;
}
}
class Node {
// 当前元素
Integer value;
// 当前最小值
Integer min;
Node(Integer value, Integer min) {
this.value = value;
this.min = min;
}
}
解答5 推荐
package edu.yuwen.sowrd.num30.sol5;
public class MinStack {
Node head;
public MinStack() {
head = null;
}
public void push(int x) {
// 链表为空，则当前元素是最小值
if (head == null) {
head = new Node(x, x, null);
return;
}
// 找个链表中的最小值和当前元素比较
Integer min = head.min;
if (x < min) {
min = x;
}
// 在表头插入新的节点
head = new Node(x, min, head);
}
public void pop() {
// 去掉表头第一个元素
head = head.next;
}
public int top() {
return head.value;
}
public int min() {
return head.min;
}
}
class Node {
// 当前元素
Integer value;
// 当前最小值
Integer min;
// 下一个节点
Node next;
Node(Integer value, Integer min, Node next) {
this.value = value;
this.min = min;
this.next = next;
}
}
网友评论