题解 | #包含min函数的栈#
包含min函数的栈
http://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49
算法思想一：定义辅助栈
解题思路：
1、要用两个栈，stack用于存储元素，mins用于存储最小值，每个位置的元素都有一个对应的最小值，也就是stack和mins的长度同步增加和减少；当需要得到目前栈中的最小值的时候，直接返回mins的栈顶元素即可
2、在mins栈中先添加一个最大值，因为以后每次添加都会和栈顶元素比较，如果栈为空的话代码要多写几行，先放一个最大值会方便一点
2、在mins栈中先添加一个最大值，因为以后每次添加都会和栈顶元素比较，如果栈为空的话代码要多写几行，先放一个最大值会方便一点
代码展示：
Python版本
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.mins = [float("inf")]
def push(self, node):
# write code here
self.stack.append(node)
self.mins.append(min(self.mins[-1], node))
def pop(self):
# write code here
self.stack.pop()
self.mins.pop()
def top(self):
# write code here
return self.stack[-1]
def min(self):
# write code here
return self.mins[-1] 复杂度分析：
时间复杂度O(1)：栈的入、出时间均为O(1)
空间复杂度O(N)：辅助栈空间，最差情况辅助站存储元素n个
算法思想二：基于链表
解题思路：
两个List一个存放存取的东西，一个存放截至到当前下标的最小值：1.入栈一个数字就入栈一个当前位置最小值；
2.出栈一个数字就出栈尾位置最小值；
代码展示：
JAVA版本
import java.util.List;
import java.util.ArrayList;
public class Solution {
// 存储最小元素数组
Listmin = new ArrayList();
// 存储入栈数组
Listnum = new ArrayList();
public void push(int node) {
num.add(node);
// 判断最小值存入min数组
if(min.size() == 0 || node < min.get(min.size() - 1)) min.add(node);
else min.add(min.get(min.size() - 1)); }
public void pop() {
num.remove(num.size() - 1);
min.remove(min.size() - 1);
}
public int top() { // 获取最后一个元素
return num.get(num.size() - 1);
}
public int min() {
return min.get(min.size() - 1);
}
} 复杂度分析：
时间复杂度O(1)：链表的添加和删除时间为O(1)
空间复杂度O(N)：辅助数组空间，最差情况下链表存储n个元素
查看18道真题和解析
