首页 > 试题广场 >

包含min函数的栈

[编程题]包含min函数的栈
  • 热度指数：648165 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素

数据范围：操作数量满足 ，输入的元素满足
进阶：栈的各个操作的时间复杂度是 ，空间复杂度是

示例:
输入:    ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
输出:    -1,2,1,-1
解析:
"PSH-1"表示将-1压入栈中，栈中元素为-1
"PSH2"表示将2压入栈中，栈中元素为2，-1
“MIN”表示获取此时栈中最小元素==>返回-1
"TOP"表示获取栈顶元素==>返回2
"POP"表示弹出栈顶元素，弹出2，栈中元素为-1
"PSH1"表示将1压入栈中，栈中元素为1，-1
"TOP"表示获取栈顶元素==>返回1
“MIN”表示获取此时栈中最小元素==>返回-1

示例1

输入

 ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

输出

-1,2,1,-1
算法知识视频讲解
查看答案及解析
添加回答
推荐
Ron头像 Ron 
import java.util.Stack;
import java.util.Arrays;
public class Solution {
/*借用辅助栈存储min的大小，自定义了栈结构
*/
    private int size;
    private int min = Integer.MAX_VALUE;
    private Stack<Integer> minStack = new Stack<Integer>();
    private Integer[] elements = new Integer[10];
    public void push(int node) {
        ensureCapacity(size+1);
        elements[size++] = node;
        if(node <= min){
            minStack.push(node);
            min = minStack.peek();
        }else{
            minStack.push(min);
        }
    //    System.out.println(min+"");
    }

    private void ensureCapacity(int size) {
        // TODO Auto-generated method stub
        int len = elements.length;
        if(size > len){
            int newLen = (len*3)/2+1; //每次扩容方式
            elements = Arrays.copyOf(elements, newLen);
        }
    }
    public void pop() {
        Integer top = top();
        if(top != null){
            elements[size-1] = (Integer) null;
        }
        size--;
        minStack.pop();    
        min = minStack.peek();
    //    System.out.println(min+"");
    }

    public int top() {
        if(!empty()){
            if(size-1>=0)
                return elements[size-1];
        }
        return (Integer) null;
    }
    public boolean empty(){
        return size == 0;
    }

    public int min() {
        return min;
    }
}

编辑于 2015-06-19 17:57:04 回复(57)
Javascript
李增坤头像 李增坤
let stack = []
function push(node)
{
    // write code here
    stack.push(node)
}
function pop()
{
    // write code here
    stack.pop()
}
function top()
{
    // write code here
    return stack.slice(-1)[0]
//     return stack[stack.length - 1]
}
function min()
{
    // write code here
    return Math.min(...stack)
}
module.exports = {
    push : push,
    pop : pop,
    top : top,
    min : min
};
发表于 2022-08-22 22:39:12 回复(0)
Javascript
Xinleidebaby头像 Xinleidebaby 
let a=[]
function push(node)
{
    // write code here
    a.push(node)
}
function pop()
{
    // write code here
    if(a.length) a.pop()
}
function top()
{
    // write code here
    if(a.length) return a[a.length-1]
}
function min()
{
    // write code here
    let m=10000
    for(let i=0;i<a.length;i++){
        if(a[i]<m) m=a[i]
    }
    return m
}

发表于 2022-08-03 09:57:49 回复(0)
Javascript
萌萌94头像 萌萌94
let items = [];
let mins = [];
function push(node)
{
    // write code here
    items.push(node);
    // 空或者<=当前最小值
    if (mins.length == 0 || node <= mins[mins.length-1]) {
        mins.push(node);
    }
}
function pop()
{
    // write code here
    if (items.length <= 0) return -1;
    
    let ret = items.pop();
    if (ret == mins[mins.length-1]) {
        mins.pop();
    }
    return ret;
}
function top()
{
    // write code here
    if (items.length == 0) return -1;
    return items[items.length-1];
}
function min()
{
    // write code here
    if (mins.length == 0) return -1;
    return mins[mins.length-1];
}

发表于 2022-05-26 12:00:12 回复(0)
Javascript
nicole27头像 nicole27 
 let stack = [];
        let length = 0;
        let mins = [];

        function push(node) {
            // write code here
            if (length == 0) {
                mins.push(node);
            } else if (node <= mins[mins.length - 1]) {
                mins.push(node);
            } else {
                mins.push(mins[mins.length - 1]);
            }
            stack.push(node);
            length++;
        }

        function pop() {
            // write code here 
            if (length !== 0) {
                length--;
                mins.pop();
                return stack.pop();
            }
        }

        function top() {
            // write code here
            if (length !== 0) return stack[length - 1];
        }

        function min() {
            // write code here
            if (length !== 0) {
                return mins[mins.length - 1];
            }
        }

发表于 2022-03-05 21:30:04 回复(0)
Javascript
你是青青头像 你是青青
我我真的读不懂题啊！！！！
发表于 2022-02-22 18:00:51 回复(0)
Javascript
牛客760559747号头像 牛客760559747号
let stack = []
function push(node)
{
    // write code here
    return stack.push(node)
}
function pop()
{
    // write code here
    if(stack.length){
        return stack.pop()
    }
}
function top()
{
    // write code here
    if(stack.length){
        return stack[stack.length-1]
    }
}
function min()
{
    // write code here
    if(stack.length){
        let min = stack[0]
        for(let i=0;i<stack.length;i++){
            if(stack[i]<min) min = stack[i]
        }
        return min
        
    }
}
module.exports = {
    push : push,
    pop : pop,
    top : top,
    min : min
};
发表于 2021-12-29 10:53:36 回复(0)
Javascript
周欣仪头像 周欣仪

参考官方的牛客题霸的方法

方法：使用辅助栈

首先需要一个正常栈normal,用于栈的正常操作，然后需要一个辅助栈minval，专门用于获取最小值，具体操作如下。

  • push操作就如图片上操作。
  • pop操作直接对应弹出就好了。
  • top操作就返回normal的栈顶
  • min操作就返回minval的栈顶
JavaScript的代码如下所示： 
var stack = [];       //存放输入数据
var minStack = [];     //存放最小的数据

function push(node)
{
     stack.push(node);
    // write code here
    if(minStack.length == 0){
        minStack.push(node);
    }else{
        let minV =minStack[minStack.length-1];
        if(node < minV){
            minStack.push(node);
        }else{
            minStack.push(minV);
        }
    }
}
function pop()
{
    // write code here
    minStack.pop();
     stack.pop();
}
function top()
{
    // write code here
    return stack[stack.length-1];
}
function min()
{
    // write code here
    return minStack[minStack.length-1];
}


发表于 2021-08-28 15:43:40 回复(0)
Javascript
牛客822067661号头像 牛客822067661号 
let arr = [];
function push(node)
{
    arr.push(node);
}
function pop()
{
    arr.pop();
}
function top()
{
    return arr[arr.length-1];
}
function min()
{
    let copy = [...arr]
    return copy.sort((a,b)=>a-b)[0]
}

发表于 2021-08-10 11:53:30 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
var stack = [];
var stack2 = [];
function push(node)
{
    // write code here
    stack.push(node);
    if(stack2.length == 0){
        stack2.push(node);
    }else{
        if(node < stack2[stack2.length - 1]){
            stack2.push(node);
        }else{
            stack2.push(stack2[stack2.length - 1]);
        }
    }
}
function pop()
{
    // write code here
    stack.pop();
    stack2.pop();
}
function top()
{
    // write code here
    return stack[stack.length - 1];
    return stack2[stack2.length - 1];
}
function min()
{
    // write code here
    
    return stack2[stack2.length - 1];
}

发表于 2021-03-16 16:31:07 回复(0)
JavaScript
奕※時＾毀￠头像 奕※時＾毀￠ 
var array=new Array();
function push(node)
{
    array.push(node);
}
function pop()
{
    return array.pop();
}
function top()
{
    return array.shift();
}
function min()
{
    for(var i=0,res=Number.MAX_VALUE;i<array.length;i++){
        if(res>array[i]){
            res=array[i]
        }
    }
    return res;
}

发表于 2020-04-29 10:48:37 回复(0)
JavaScript
kts。头像 kts。 
var stack_ = [],min_stack=[],min_flag=-1,flag =-1;
function push(node)
{
	if (flag==-1) {
		min_flag++;
		min_stack[min_flag]=node
	}else{
		if(min_stack[min_flag]>=node){
			min_flag++;
			min_stack[min_flag]=node;
		}
	}
	stack_[flag]=node;
	flag++;
}
function pop()
{
	if(flag<0) return null;
	if (stack_[flag]==min_stack[min_flag]) {
		min_flag--;
	}
	return stack_[flag--];
}
function top()
{
	return stack_[flag]
}
function min()
{
	if (flag<0) return null;
	return min_stack[min_flag];
}
最小数入栈规则：
1、当push一个数的时候，如果栈为空，这个数即为最小值，放入最小值栈
2、当入栈元素不小于最小数栈顶元素时入最小数栈。。
这样当出栈时，就比较出栈元素是否等于最小值，如果等于，最小数栈出栈一个，出栈之后，栈顶元素即为上一次的最小值。
借用最小数栈解决当最小值出栈之后，无法用复杂度为O（1）的方法确定最小值的问题
发表于 2020-02-20 18:28:20 回复(0)
JavaScript
Bytedancer2021头像 Bytedancer2021 
let stack = [];
let indexList = [];
function push(node)
{
    // write code here
    stack.push(node);
    let index;
    for(index=0; index<indexList.length; index++){
        if(node < stack[indexList[index]]){
            break;
        }
    }
    indexList.splice(index, 0, stack.length-1);
}
function pop()
{
    // write code here
    let index = indexList.indexOf(stack.length -1);
    indexList.splice(index, 1);
    return stack.pop();
}
function top()
{
    // write code here
    return stack[stack.length -1];
}
function min()
{
    // write code here
    return stack[indexList[0]];
}

发表于 2019-09-16 20:44:50 回复(0)
JavaScript
低温火傷头像 低温火傷
// min 函数的时间复杂度为O(1)，意味着不能把查找最小值操作放在这个函数中
// 将最小值作为数组的一个属性，在push，pop 操作时，为其赋值

var arr = []
function push(node)
{
    // write code here
    if(!arr.min){
        arr.min = node
    }else{
        arr.min = arr.min < node ? arr.min : node
    }
    arr.push(node)
    return arr
}
function pop()
{
    // write code here
    if(arr.length == 0){
        return null 
    }
    var del = arr.pop()
    if(del == arr.min){
        arr.min = Math.min(...arr)
    }
    return del
}
function top()
{
    // write code here
    return arr[arr.length-1]
}
function min()
{
    // write code here
    return arr.min 
}
发表于 2019-08-09 15:52:26 回复(0)
JavaScript
不去大厂不换昵称头像 不去大厂不换昵称
1.定义两个栈，一个栈用于存储数据，另一个栈用于存储每次数据进栈时栈的最小值
2.每次数据进栈时，将此数据和最小值栈的栈顶元素比较，将二者比较的较小值再次存入最小值栈
4.数据栈出栈，最小值栈也出栈。
3.这样最小值栈的栈顶永远是当前栈的最小值。 

var dataStack = [];
var minStack = [];

function push(node)
{
    dataStack.push(node);
    if(minStack.length === 0 ||  node < min()){
        minStack.push(node);
    }else{
        minStack.push(min());
    }
}
function pop()
{
    minStack.pop();
    return dataStack.pop();
}
function top()
{
    var length = dataStack.length;
    return length>0&&dataStack[length-1]
}
function min()
{
    var length = minStack.length;
    return length>0&&minStack[length-1]
}

发表于 2019-02-12 22:44:55 回复(0)
JavaScript
布衣大侠头像 布衣大侠 
//栈  3，4，2，5，1
//    辅助栈 3，3，2，2，1
//每入栈一次，就与辅助栈顶比较大小，
//如果小于辅助栈顶，就二个栈都入栈
//如果大于辅助栈顶,辅助栈就入栈当前的辅助栈顶
//当出栈时，辅助栈也要出栈

var  arr=[];
var tempArr=[]; 
function push(node)
{
  arr.push(node);
   if(!tempArr.length){  //刚开始 辅助栈为空 就添加
        tempArr.push(node);
   }else if(node<=tempArr[tempArr.length-1]){  //接下来，判断node值和辅助栈顶元素大小 
        tempArr.push(node);
   }else{
       tempArr.push(tempArr[tempArr.length-1]);
   }
    
}
function pop()
{
    arr.pop();
   tempArr.pop();
    
}
function top()
{
 return arr[arr.length-1]; 
}
function min()
{
  return tempArr[tempArr.length-1];
}

发表于 2018-09-25 17:22:26 回复(0)
JavaScript
Mr.Voyz头像 Mr.Voyz 
function push(node)
{
    // write code here
    dataStore.push(node);
    if (assistStack.length === 0) {
    	assistStack.push(node)
    }
    else if(node < assistStack[assistStack.length-1]) {
    	assistStack.push(node);
    }
    else{
    	assistStack.push(assistStack[assistStack.length-1]);
    }

}
function pop()
{
    // write code here
    dataStore.pop();
    assistStack.pop();
}
function top()
{
    // write code here
    return dataStore[dataStore.length-1];

}
function min()
{
    // write code here
    return assistStack[assistStack.length-1];
}

var dataStore = [];
var assistStack = [];
var pointer = 0;
发表于 2018-09-12 09:22:51 回复(0)
JavaScript
是函数不是方法头像 是函数不是方法
欸？是我理解错题意还是js原本就是这么优秀？ 
var arr = [];
function push(node)
{
    arr.push(node);
}
function pop()
{
    arr.pop();
}
function top()
{
    return arr[0];
}
function min()
{
    return Math.min(...arr);
}

发表于 2018-08-07 15:16:43 回复(0)
JavaScript
求一个offer啊啊啊头像 求一个offer啊啊啊 
var result = [];

    function push(node) {
      // write code here
      return result.push(node);
    }

    function pop() {
      // write code here
      return result.pop();
    }

    function top() {
      // write code here
      return result.length > 0 ? result[length - 1] : null;
    }

    function min() {
      // write code here
      if (result.length == 0 || result == null) return;
      var min = result[0];
      result.map(function(a) {
        if (a < min) min = a;
      });
      return min;
    }

发表于 2018-06-02 13:01:03 回复(0)
JavaScript
William1780头像 William1780 
let staDat = [],
    staMin = [];
function push(node)
{
    staDat.push(node);
    if(node < min() || staMin.length===0)
        staMin.push(node)
    else
        staMin.push(min());
}
function pop()
{
    if(staDat.length === 0) return null;
    staMin.pop();
    return staDat.pop();
}
function top()
{
    if(staDat.length === 0) return null;
    return staDat[staDat.length-1];
}
function min()
{
    if(staMin.length === 0) return null;
    return staMin[staMin.length-1];
}
编辑于 2018-04-25 14:18:50 回复(0)
JavaScript
程震宇头像 程震宇 

	var ans=[];





	 





	function push(node)





	{





	    // write code here





	    ans.push(node);





	}





	function pop()





	{





	    // write code here





	    return ans.pop();





	}





	function top()





	{





	    // write code here





	    returnans[ans.length-1];





	}





	function min()





	{





	    // write code here





	    var minVal;





	    if(ans.length>0)





	        minVal = ans[0];





	    for(var i=0;i<ans.length;i++){





	        if(minVal > ans[i])





	            minVal=ans[i];





	    }





	    returnminVal;





	}





	module.exports = {





	    push : push,





	    pop : pop,





	    top : top,





	    min : min





	};

发表于 2017-03-28 16:29:41 回复(0)
提交观点

问题信息

栈
难度：
21条回答 153469浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号