题解 | #包含min函数的栈#
包含min函数的栈
http://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49
思路：
- 建两个栈
- 思路一：
- 1、push时主栈存放数值，辅助栈存放对应数值时的最小值（需要辅助栈起始值为无穷大）
- 2、pop时主栈弹出，辅助栈也弹出
- 思路二：
- 1、push时主栈存放数值，如果辅助栈没有值或者值小于等于辅助栈栈顶值则存入
- 2、pop时主栈弹出，主栈弹出值若等于辅助栈栈顶值，辅助栈也弹出
- 栈顶值top为主栈栈顶值
- 最小值min为辅助栈栈顶值
var data_stack = [] // 主栈
var min_stack = [Infinity] // 辅助栈
function push(node)
{
// 主栈x_stack存放值
data_stack.push(node)
// 辅助栈min_stack存入与辅助栈min_stack栈顶作比较后的最小值
min_stack.push(Math.min(min_stack[min_stack.length - 1],node))
}
function pop()
{
// 两者都弹出值
data_stack.pop()
min_stack.pop()
}
function top()
{
// 返回主栈x_stack栈顶
return data_stack[data_stack.length - 1]
}
function min()
{
// 返回辅助栈min_stack栈顶
return min_stack[min_stack.length - 1]
}
module.exports = {
push : push,
pop : pop,
top : top,
min : min
};
var data_stack = [] // 主栈
var min_stack = [] // 辅助栈
function push(node)
{
// 主栈x_stack存放值
data_stack.push(node)
// 辅助栈min_stack如果没有值或新值比辅助栈min_stack栈顶值小则存入值
if(!min_stack.length || node <= min_stack[min_stack.length - 1]){
min_stack.push(node)
}
}
function pop()
{
// 主栈x_stack弹出值若与辅助栈min_stack栈顶值一致，辅助栈min_stack也弹出值
if(data_stack.pop() == min_stack[min_stack.length - 1]){
min_stack.pop()
}
}
function top()
{
// 返回主栈x_stack栈顶
return data_stack[data_stack.length - 1]
}
function min()
{
// 返回辅助栈min_stack栈顶
return min_stack[min_stack.length - 1]
}
module.exports = {
push : push,
pop : pop,
top : top,
min : min
};
投递华为等公司10个岗位 >