题解 | #包含min函数的栈#
包含min函数的栈
http://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49
描述
这是一篇面对初级coder的题解。
知识点：栈
难度：二星
题解
题目：
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
这道题考察栈的知识：
本题难点是如何维护最小元素，如果用一个单一值来记录最小值，
最小值出栈后就会用O(n)复杂度重新查找，最坏情况时间复杂度O(n)，不符合题目要求
双栈法
可以采用一个最小元素的栈来维护这样一个数据结构
#include <stack>
class Solution {
stack<int> data,mindata;//双栈法，维护一个数据栈和一个最小值栈
public:
void push(int value) {
data.push(value);//数据栈入栈
if(mindata.size()==0||value<=mindata.top())//如果入栈值小于等于最小值，或当前栈为空
mindata.push(value);//，最小值栈入栈
}
void pop() {
if(mindata.top()==data.top())//如果出栈是当前的最小值
mindata.pop();//最小值栈出栈
data.pop();//数据栈出栈
}
int top() {
return data.top();//返回数据栈栈顶元素
}
int min() {
return mindata.top();//返回最小值栈栈栈顶元素
}
};
- 时间复杂度: O(1)
- 空间复杂度: O(n)，最坏情况要保存全部值。
- 运行时间7ms 占用内存620KB
残差法
能否在时间复杂度不变的前提下，进一步缩小空间复杂度？
可以在栈中只记录与最小值的差，
那么就存在一个问题，随着元素的输入，mindata的值是在变化的 每次push()入栈一个更小的元素都需要把stack中的差更新一遍吗?
答案是不需要。
试想，当我们引入一个更小的元素value时，它与mindata的差dis = x - mindata显然是个负数，那么这时就要更新mindata=value
答案是不需要。
试想，当我们引入一个更小的元素value时，它与mindata的差dis = x - mindata显然是个负数，那么这时就要更新mindata=value
那么如果value要出栈的话，stack中保存的是value进栈之前与上一个mindata的差，这时只要将mindata= mindata-value就可以将mindata回退到value入栈之前的最小值。
栈中值为负数的时候 top 和pop都需要特殊判断
#includeclass Solution {
stackdata;//残差法，维护一个数据栈（记录每个元素与最小值差）
int mindata;//和一个最小值
public:
void push(int value) {
if(data.size()==0)//如果当前栈为空
mindata=value;//更新当前最小值
data.push(value-mindata);//数据栈入栈
if(value-mindata<0)//入栈值小于等于最小值 mindata=value;//更新当前最小值 } void pop() { if(0>=data.top())//如果出栈是当前的最小值
mindata=mindata-data.top();//最小值更新
data.pop();//数据栈出栈
}
int top() {
if(0>=data.top())//如果出栈是当前的最小值
return mindata;//返回最小值
else
return mindata+data.top();//返回数据栈栈顶元素
}
int min() {
return mindata;//返回最小值
}
};
- 时间复杂度: O(1)
- 空间复杂度: O(1),只需要一个额外的空间维护mindata即可。
- 运行时间3ms 占用内存492KB
总结
栈的特点是后进先出 前面的数据在后面的数据处理完之前无需更改
需要利用栈的特性
阿Q的题解 文章被收录于专栏
阿Q秋招刷过的题
