首页 > 试题广场 > 包含min函数的栈
[编程题]包含min函数的栈
定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(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 回复(37)
class Solution {
public:
    
    stack<int> stack1,stack2;
    
    void push(int value) {
        stack1.push(value);
        if(stack2.empty())
            stack2.push(value);
        else if(value<=stack2.top())
        {
            stack2.push(value);
        }
    }
    
    void pop() {
        if(stack1.top()==stack2.top())
            stack2.pop();
        stack1.pop();
        
    }
    
    int top() {
        return stack1.top();        
    }
    
    int min() {
        return stack2.top();
    } 
    
};
应用一个辅助栈,压的时候,如果A栈的压入比B栈压入大,B栈不压,,,,小于等于,AB栈同时压入,出栈,如果,AB栈顶元素不等,A出,B不出。
编辑于 2016-08-15 19:38:47 回复(41)

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。

思路

    看到这个问题, 我们最开始可能会想, 添加一个成员变量用于保存最小元素, 每次压栈时如果压栈元素比当前最小元素更小, 就更新最小元素. 
    但是这样会有一个问题, 如果最小元素被弹出了呢, 如何获得下一个最小元素呢? 分析到这里可以发现, 仅仅添加一个成员变量存放最小元素是不够的, 我们需要在最小元素弹出后还能得到次小元素, 次小的弹出后, 还要能得到次次小的. 
    因此, 用另一个栈来保存这些元素是再合适不过的了. 我们叫它最小元素栈. 
    每次压栈操作时, 如果压栈元素比当前最小元素更小, 就把这个元素压入最小元素栈, 原本的最小元素就成了次小元素. 同理, 弹栈时, 如果弹出的元素和最小元素栈的栈顶元素相等, 就把最小元素的栈顶弹出.

代码

class Solution {
public:
    void push(int value) {
        s.push(value);
        if(sMin.empty())
            sMin.push(value);
        else if(value <= sMin.top())
            sMin.push(value);
    }
    void pop() {
        if(s.top() == sMin.top())
            sMin.pop();
        s.pop();
    }
    int top() {
        return s.top();
    }
    int min() {
        return sMin.top();
    }
private:
    stack<int> s;
    stack<int> sMin;
};
编辑于 2018-02-09 10:17:14 回复(6)
import java.util.Stack;

思路:用一个栈data保存数据,用另外一个栈min保存依次入栈最小的数
比如,data中依次入栈,5,  4,  3, 8, 10, 11, 12, 1
       则min依次入栈,5,  4,  3,no,no, no, no, 1

no代表此次不如栈
每次入栈的时候,如果入栈的元素比min中的栈顶元素小或等于则入栈,否则不如栈。

public class Solution {
	Stack<Integer> data = new Stack<Integer>();
    Stack<Integer> min = new Stack<Integer>();
    Integer temp = null;
    public void push(int node) {
        if(temp != null){
            if(node <= temp ){
                temp = node;
                min.push(node);
            }
            data.push(node);
        }else{
            temp = node;
            data.push(node);
            min.push(node);
        }
    }
    
    public void pop() {
        int num = data.pop();
        int num2 = min.pop();
        if(num != num2){
           min.push(num2); 
        }
    }
    
    public int top() {
        int num = data.pop();
        data.push(num);
        return num;
    }
    
    public int min() {
        int num = min.pop();
        min.push(num);
        return num;
    }
}

发表于 2015-09-16 15:19:43 回复(35)
思路:利用一个辅助栈来存放最小值

    栈  3,4,2,5,1
    辅助栈 3,3,2,2,1
每入栈一次,就与辅助栈顶比较大小,如果小就入栈,如果大就入栈当前的辅助栈顶
当出栈时,辅助栈也要出栈
这种做法可以保证辅助栈顶一定都当前栈的最小值

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.assist = []
        
    def push(self, node):
        min = self.min()
        if not min or node < min:
            self.assist.append(node)
        else:
            self.assist.append(min)
        self.stack.append(node)
        
    def pop(self):
        if self.stack:
            self.assist.pop()
            return self.stack.pop()
    
    def top(self):
        # write code here
        if self.stack:
            return self.stack[-1]
        
    def min(self):
        # write code here
        if self.assist:
            return self.assist[-1]

发表于 2016-07-25 10:04:21 回复(18)
import java.util.Stack;

public class Solution {
	Stack<Integer> dataStack = new Stack<Integer>();
	Stack<Integer> minStack = new Stack<Integer>();
    
        public void push(int node) {
		dataStack.push(node);
		if(minStack.isEmpty() || node < minStack.peek()){
			minStack.push(node);
		}
		else{
			minStack.push(minStack.peek());
		}
	}

	public void pop() {
		dataStack.pop();
		minStack.pop();
	}

	public int top() {
		return dataStack.peek();
	}

	public int min() {
		return minStack.peek();
	}
}

发表于 2016-11-29 17:06:36 回复(19)
/*
* 1.dataStack为存储数据的栈,minStack为存储最小值的栈;
* 2.push的时候将value值与minStack中的top值比较,小则minStack push value,大则push top值
*/
class Solution {
public:
    stack<int> dataStack, minStack;
    void push(int value) {
        dataStack.push(value);
        if (minStack.empty()) {
            minStack.push(value);
        }
        else{
            int min = minStack.top();
            value<=min?minStack.push(value):minStack.push(min);
        }
        
    }
    void pop() {
        dataStack.pop();
        minStack.pop();
    }
    int top() {
        return  dataStack.top();
    }
    int min() {
        return minStack.top();
    }
};

发表于 2015-10-23 17:04:21 回复(21)

python solution:

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.arr=[]
    def push(self, node):
        # write code here
        self.arr.append(node)
    def pop(self):
        # write code here
        return self.arr.pop()
    def top(self):
        return self.arr[-1]
    def min(self):
        # write code here
        return min(self.arr)
发表于 2017-10-07 19:19:48 回复(14)

Python大法好

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.minList = []

    def push(self, node):
        if not self.minList:
            self.minList.append(node)
        else:
            self.minList.append(min(self.minList[-1], node))
        self.stack.append(node)

    def pop(self):
        if not self.stack:
            return None
        self.minList.pop()
        return self.stack.pop()

    def top(self):
        if not self.stack:
            return None
        return self.stack[-1]

    def min(self):
        if not self.minList:
            return None
        return self.minList[-1]
发表于 2018-01-01 16:54:19 回复(5)
每个函数只需一句

first 元素
second 当前最小值

class Solution {
    typedef pair<int, int> pii;
    stack<pii> s;
public:
    void push(int value) {
        s.push(pii(value, ::min(value, s.empty() ? value : min())));
    }
    void pop() {
        s.pop();
    }
    int top() {
        return s.top().first;
    }
    int min() {
        return s.top().second;
    }
};

编辑于 2017-09-03 15:30:56 回复(22)
ArrayList实现
import java.util.ArrayList;

public class Solution {

    ArrayList<Integer> list = new ArrayList<Integer>();
    
    public void push(int node) {
        list.add(0,node);
    }
    
    public void pop() {
        list.get(0);
        list.remove(0);
    }
    
    public int top() {
        return list.get(0).intValue();
    }
    
    public int min() {
        int temp = top();
        for(int i=1;i<list.size();i++){
            if(temp>list.get(i).intValue()){
                temp = list.get(i).intValue();
            }
        }
        return temp;
    }
}

发表于 2016-08-31 11:10:12 回复(7)
简洁的方式:(minNum的即时实现会比延迟实现更方便,延迟实现需要一个额外的栈保存原有栈的内容)
import java.util.Stack;

public class Solution {
    //记得指定泛型,以免后续需要强制类型转换
	Stack<Integer> stack=new Stack<>();
    Stack<Integer> minNum=new Stack<>();
    
    public void push(int node) {
        stack.push(node);
        if(minNum.isEmpty()) minNum.push(stack.peek()); //Java中获取栈顶:peek()
        else if(stack.peek()<minNum.peek()) minNum.push(stack.peek());
        else minNum.push(minNum.peek());
    }
    
    public void pop() {
        stack.pop();
        minNum.pop();//同步弹出元素
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
       return  minNum.peek();
    }
}

发表于 2016-09-07 16:14:49 回复(5)

两个栈实现 辅助栈放所有的最小值们

class Solution {
public:
    stack<int> s;
    stack<int> s_min;
    void push(int value) {
        if(s.empty() || value <= s_min.top()) s_min.push(value);
        s.push(value);
    }
    void pop() {
        if(s.top() == s_min.top()) s_min.pop();
        s.pop();
    }
    int top() {
        return s.top();
    }
    int min() {
        return s_min.top();
    }
};
发表于 2018-12-02 15:39:32 回复(0)
/*

解题思路:

我们可以设计两个栈:StackDate和StackMin,一个就是普通的栈,另外一个存储push进来的最小值。

首先是push操作:

每次压入的数据newNum都push进StackDate中,然后判断StackMin是否为空,如果为空那也把newNum同步压入 StackMin里;如果不为空,就先比较newNum和StackMin中栈顶元素的大小,如果newNum较大,那就不压入StackMin里,否则 就同步压入StackMin里。如:
这里写图片描述

接着是pop操作

先将StackDate中取出的数据value与StackMin的栈顶元素比较,因为对应push操作,value不可能小于 StackMin中的栈顶元素,最多是相等。如果相等,那么StackMin中也取出数据,同时返回value,否则只是返回value就可以了。

最后是getMin操作

  由上就可知,StackMin中存储的数据就是当前最小的,所以只要返回StackMin中的栈顶元素就可以了。
*/
import java.util.Stack;

public class Solution {

    private Stack<Integer> stackDate;
    private Stack<Integer> stackMin;
    
    public Solution(){
    	stackDate = new Stack<>();
    	stackMin = new Stack<>();
    }
    public void push(int node) {
    	stackDate.push(node);
    	if(stackMin.isEmpty()){
    		stackMin.push(node);
    	}else if(node <= stackMin.peek()){
    		stackMin.push(node);
    	}
    }
    
    public void pop() {
    	 if(stackDate.isEmpty()){
         	throw new RuntimeException("This stack is empty!");
         }
    	 if(stackDate.peek() == stackMin.peek()){
    		 stackMin.pop();
    	 }
    	 stackDate.pop();
    }
    
    public int top() {
    	if(stackDate.isEmpty()){
         	throw new RuntimeException("This stack is empty!");
         }
    	int value = stackDate.pop();
    	 if(value == stackMin.peek()){
    		 stackMin.pop();
    	 }
    	return value;
    }
    
    public int min() {
        if(stackMin.isEmpty()){
        	throw new RuntimeException("This stack is empty!");
        }else{
        	return stackMin.peek();
        }
    }
}

发表于 2016-10-13 09:07:18 回复(3)
import java.util.Stack;

public class Solution {

    Stack s1=new Stack();
    Stack min=new Stack();
    public void push(int node) {
        if(min.empty()){
            min.push(node);
        }else{
            int top=(int)min.peek();
            if(node<top){
               min.push(node); 
            }else{
                min.push(top);
            }
        }
        s1.push(node);
    }
    
    public void pop() {
        if(!(s1.empty())){
            s1.pop();
            min.pop();
        }
    }
    
    public int top() {
        return (int)s1.peek();
    }
    
    public int min() {
       if(min.empty()){
    	   return 0;
       }
       return (int)min.peek();     
    }
}

发表于 2015-11-27 20:53:39 回复(4)
https://blog.csdn.net/qq_41822235/article/details/82468584本博客对剑指offer经典解法利用两个栈来回倒,辅助栈内存在大量冗余的最小值的情况做下处理。
发表于 2018-09-07 10:52:41 回复(0)
class Solution {
public:
    void push(int value) {
        stk.push(value);
        if(smin.empty())
            smin.push(value);
        if(value<smin.top())
            smin.push(value);
    }
    void pop() {
        if(stk.top()==smin.top())
            smin.pop();
        stk.pop();
    }
    int top() {
        return stk.top();
    }
    int min() {
        return smin.top();
    }
    private:
    stack<int> stk;
    stack<int> smin;
};

编辑于 2018-02-26 19:49:20 回复(0)
让定义栈然后使用栈的相关方法的话感觉怪怪的,所以纯用数组实现了这个
import java.util.Stack;

public class Solution {
    int data[]=new int[10000];
    int min[]=new int[10000];
    int index=0;
    
    public void push(int node) {
        data[index]=node;
        if(index==0){
            min[index]=node;
        }else{
            if(node<min[index-1]){
                min[index]=node;
            }else{
                min[index]=min[index-1];
            }
        }
        index++;
    }
    
    public void pop() {
        index--;
        if(min[index]==data[index]){
            min[index]=min[index-1];
        }
    }
    
    public int top() {
        return data[index-1];
    }
    
    public int min() {
        return min[index-1];
    }
}
发表于 2016-07-23 14:37:44 回复(0)
骚套路...
class Solution {
public:
    void push(int value) {
        deq.push_back(value);
    }
    void pop() {
       deq.pop_back(); 
    }
    int top() {
        return deq.front();
    }
    int min() {
        return *std::min_element(deq.begin(),deq.end());
    }
    deque<int> deq;
};

发表于 2018-09-01 11:51:41 回复(2)
使用两个栈,一个栈用作正常接收数据,另外一个栈作为辅助栈记录每次添加数据时候的最小值,可以实现从栈中以O(1)的时间复杂度得到栈中的最小值,需额外空间O(N)。
import java.util.Stack;

public class Solution {
    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> help = new Stack<Integer>();
    
    public void push(int node) {
        if (!stack.isEmpty() && !help.isEmpty()) {
            stack.push(node);
            if (node < help.peek()) {
                help.push(node);
            } else {
                help.push(help.peek());
            }
        } else {
            stack.push(node);
            help.push(node);
        }
    }
    
    public void pop() {
        if (!stack.isEmpty() && !help.isEmpty()) {
            stack.pop();
            help.pop();
        }
    }
    
    public int top() {
        int res = 0;
        if (!stack.isEmpty() && !help.isEmpty()) {
            res = stack.peek();
        }
        return res;
    }
    
    public int min() {
        int min = Integer.MAX_VALUE;
        if (!stack.isEmpty() && !help.isEmpty()) {
            min = help.peek();
        }
        return min;
    }
}

发表于 2018-07-13 23:42:36 回复(0)
package go.jacob.day1130;

import java.util.Stack;

/**
 * 程序员代码面试指南
 * 
 * @author Jacob 
 * 设计一个有getMin功能的栈
 *
 */
public class Demo2 {
    // 定义两个栈,一个是正常的栈,另一个是用来返回最小值的栈
    private Stack<Integer> stackData = new Stack<Integer>();
    private Stack<Integer> stackMin = new Stack<Integer>();

    public void push(int node) {
        stackData.push(node);
        // 当stackMin为空,或者当前值小于stackMin栈顶元素是,入栈
        if (stackMin.isEmpty() || (!stackMin.isEmpty() && stackMin.peek() >= node))
            stackMin.push(node);
    }

    /*
     * 如果栈为空,抛异常 
     * 如果stackMin的栈顶元素与stackkData栈顶元素相同,同时pop 
     * 否则只弹stackData
     */
    public void pop() {
        if (stackData.isEmpty())
            throw new RuntimeException("stack is empty");
        if (stackData.peek() == stackMin.peek())
            stackMin.pop();
        stackData.pop();

    }

    public int top() {
        if (stackData.isEmpty())
            throw new RuntimeException("stack is empty");
        return stackData.peek();
    }

    public int min() {
        if (stackMin.isEmpty())
            throw new RuntimeException("stack is empty");
        return stackMin.peek();
    }
}

发表于 2017-11-30 11:07:14 回复(0)