首页 > 试题广场 >

包含min函数的栈

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

此栈包含的方法有:
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)
让定义栈然后使用栈的相关方法的话感觉怪怪的,所以纯用数组实现了这个
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 回复(1)
骚套路...
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 回复(3)
使用两个栈,一个栈用作正常接收数据,另外一个栈作为辅助栈记录每次添加数据时候的最小值,可以实现从栈中以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)
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 回复(59)

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

解题思路

思路:利用一个辅助栈来存放最小值

栈 3,4,2,5,1

辅助栈 3,3,2,2,1

每入栈一次,就与辅助栈顶比较大小,如果小就入栈,如果大就入栈当前的辅助栈顶;

当出栈时,辅助栈也要出栈

这种做法可以保证辅助栈顶一定都当前栈的最小值

我的答案

import java.util.Stack;

public class Solution {


    //存放元素
    Stack<Integer> stack1 = new Stack<Integer>();
    //存放当前stack1中的最小元素
    Stack<Integer> stack2 = new Stack<Integer>();

    //stack1直接塞,stack2要塞比栈顶小的元素,要不然就重新塞一下栈顶元素
    public void push(int node) {
        stack1.push(node);
        if(stack2.isEmpty() || stack2.peek() > node){
            stack2.push(node);
        }else{
            stack2.push(stack2.peek());
        }

    }

    //都要pop一下
    public void pop() throws Exception{
        if(stack1.isEmpty()){
           throw new Exception("no element valid"); 
        }
        stack1.pop();
        stack2.pop();
    }


    public int top(){
        if(stack1.isEmpty()){
           return 0;
        }
        return stack1.peek();
    }

    public int min(){
        if(stack2.isEmpty()){
           return 0;
        }
        return stack2.peek();
    }
}
发表于 2019-03-07 20:15:03 回复(0)
class Solution {
public:
    stack<int> s1;
    stack<int> s2;
    void push(int value) {
        s1.push(value);
        if(s2.empty() || s2.top()>value)
            s2.push(value);
        else
            s2.push(s2.top());
    }
    void pop() {
        s1.pop();
        s2.pop();
    }
    int top() {
        return s1.top();
    }
    int min() {
        return s2.top();
    }
};

发表于 2022-07-10 20:41:37 回复(0)
import java.util.Stack;

public class Solution {

    Stack<Integer> stack = new Stack<>();
    private int minNum = Integer.MAX_VALUE;
    public void push(int node) {
        stack.push(node);
        minNum = Math.min(minNum, node);
    }

    public void pop() {
        stack.pop();
        int temp_min = Integer.MAX_VALUE;
        for (Integer num : stack) {
            temp_min = Math.min(temp_min, num);
        }
        minNum = temp_min;
    }

    public int top() {
        return stack.lastElement();
    }

    public int min() {
        return minNum;
    }
}

发表于 2022-06-04 18:29:27 回复(0)
import java.util.*;

public class Solution {
    
    Stack<Integer> stack = new Stack<>();
    
    public void push(int node) {
        stack.push(node);
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        //重点:stack转为list集合然后遍历集合比较最小值就比遍历栈要简单。
        List<Integer> list = new ArrayList<>(stack);
         int min = list.get(0);
        for(int i=1;i<list.size();i++){
            if(list.get(i) < min)
                min = list.get(i);
        }
        return min;
    }
}
发表于 2022-03-11 21:29:55 回复(0)
无脑遍历所有数据,反正题目也说了,栈中一定有元素。
import java.util.Stack;

public class Solution {

    Stack<Integer> stack = new Stack();
    
    public void push(int node) {
        stack.push(node);
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        int min = Integer.MAX_VALUE;
        for(Integer num : stack){
            if(min > num)
                min = num;
        }
        return min;
    }
}

发表于 2021-11-17 18:55:34 回复(0)

python 利用辅助栈实现

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.A,self.B=[],[]
    def push(self, node):
        # write code here
        self.A.append(node)
        if not self.B or self.B[-1]>=node:
            self.B.append(node)
    def pop(self):
        # write code here
        if self.A.pop()==self.B[-1]:
            self.B.pop()
    def top(self):
        # write code here
        return self.A[-1]
    def min(self):
        # write code here
        return self.B[-1]
发表于 2021-11-07 23:26:54 回复(0)
import java.util.Arrays;
import java.util.Stack;

public class Solution {

    private int capacity = 10;  // 数据栈初始容量
    private int[] data = new int[capacity]; // 数据栈
    private int size = 0;   // 数据栈中元素的个数 & 指向栈顶下一个元素的指针
    private final Stack<Integer> minStack = new Stack<>();    // 辅助栈

    public void push(int node) {
        // 如果容量不足则扩容为之前容量的2倍
        if (size == capacity) {
            capacity <<= 1;    
            data = Arrays.copyOf(data, capacity);
        }
        // 压入数据栈
        data[size++] = node;

        // 如果辅助栈为空或node小于等于辅助栈栈顶元素,则压入辅助栈
        if (minStack.empty() || node <= minStack.peek())
            minStack.push(node);

    }

    public void pop() {
        // 弹出数据栈栈顶,同时如果辅助栈栈顶元素等于数据栈栈顶元素,则也弹出
        if (minStack.peek() == data[--size])
            minStack.pop();
    }

    public int top() {
        return data[size - 1];
    }

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

发表于 2021-10-07 12:09:24 回复(0)

Js 用数组。pop出来还要再压进去,没人写js题解,我来搞一个

let s1=[],s2=[]

function push(node)
{
    // write code here
    let temp=s2.pop()
    if(!s2.length||node<=temp){
        s2.push(temp)
        s2.push(node)
    }else{
        s2.push(temp)
    }
    s1.push(node)
}
function pop()
{
    // write code here
    let temp1=s1.pop()
    let temp2=s2.pop()
    if(temp1!==temp2)
        s2.push(temp2)
}
function top()
{
    // write code here
    let temp=s1.pop()
    s1.push(temp)
    return temp
}
function min()
{
    // write code here
    let temp=s2.pop()
    s2.push(temp)
    return temp
}
module.exports = {
    push : push,
    pop : pop,
    top : top,
    min : min
};
发表于 2021-09-29 10:20:39 回复(0)
class Solution {
public:
    stack<int> s;
    stack<int> m;
    void push(int value) {
        s.push(value);
        if(!m.empty()){
            m.push(value<m.top()?value:m.top());
        }else{
            m.push(value);
        }
    }
    void pop() {
        s.pop();
        m.pop();
    }
    int top() {
        return s.top();
    }
    int min() {
        return m.top();
    }
};

发表于 2021-09-13 20:42:25 回复(1)
import java.util.*;

public class Solution {
    private Deque<Integer> stack;
    private Deque<Integer> help;
    
    public Solution() {
        stack = new LinkedList<>();
        help = new LinkedList<>();
        help.push(Integer.MAX_VALUE);
    }
    
    public void push(int node) {
        stack.push(node);
        if(node < help.peekFirst()) {
            help.push(node);
        } else {
            help.push(help.peekFirst());
        }
    }
    
    public void pop() {
        stack.pop();
        help.pop();
    }
    
    public int top() {
        return stack.peekFirst();
    }
    
    public int min() {
        return help.peekFirst();
    }
}

发表于 2021-08-09 20:31:11 回复(0)
import java.util.Stack;

public class Solution {

    Stack<Integer> min = new Stack<Integer>();
     Stack<Integer> v = new Stack<Integer>();
    
    public void push(int node) {
        if(min.isEmpty()){
            min.add(node);
        }else{
            if(min.peek() >= node){
                min.add(node);
            }
        }
        v.add(node);
    }
    
    public void pop() {
         if(v.isEmpty()){
             return;
         }
        if(v.peek() == min.peek()){
            min.pop();
        }
        v.pop();
    }
    
    public int top() {
        if(v.isEmpty()){
            return -1;
        }
        return v.peek();
    }
    
    public int min() {
        if(min.isEmpty()){
            return -1;
        }
        return min.peek();
    }
}

发表于 2021-07-01 13:43:56 回复(0)
Python
发现很多同学忽略了题目的要求O(1),例如当你使用Python的min函数时,时间复杂度已经达到O(n)了
我这里的思路也是一个辅助栈的思路:PUSH的时候将min的信息也包含在里面
正常栈:3,-1,2,0
减去当前min值
辅助栈:0,-4,3,1
每次要输出的时候,与min值进行相加即可还原原来的值
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []
        self.minnum = 0
    def push(self, node):
        # write code here
        if not self.stack:
            self.minnum = node
        self.stack.append(node - self.minnum)
        if node < self.minnum:
            self.minnum = node
    def pop(self):
        # write code here
        num = self.stack.pop()
        if num < 0:
            self.minnum = self.minnum - num
#         return num - self.minnum
    def top(self):
        # write code here
        minnum = self.minnum
        if self.stack[-1] < 0:
            minnum = self.minnum - self.stack[-1]
        return self.stack[-1]+minnum
    def min(self):
        return self.minnum
        # write code here


发表于 2021-06-19 01:55:09 回复(0)
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)
import java.util.Stack;

public class Solution {

    Stack<Integer> normal = new Stack();
    Stack<Integer> minval = new Stack();
    public void push(int node) {
        normal.push(node);
        if(minval.size()>0&&minval.peek()<node){
            minval.push(minval.peek());
        }else{
            minval.push(node);
        }
    }
    
    public void pop() {
        if(!normal.isEmpty()){
            normal.pop();
            minval.pop();
        }
    }
    
    public int top() {
        return normal.peek();
        
    }
    
    public int min() {
        return minval.peek();
    }
}

发表于 2021-02-19 17:42:00 回复(0)
public class Solution {
    Stack<Integer>minstk = new Stack<>();// 永远插入最小元素
    Stack<Integer>xstk = new Stack<>();//插入当前元素
    boolean flag = true;
   
    public void push(int node) {
       xstk.push(node);
       if(flag){
           minstk.push(Math.min(Integer.MAX_VALUE,node));
           this.flag = false;
       }
       minstk.push(Math.min(minstk.peek(),node));
    }
    
    public void pop() {
        minstk.pop();
        xstk.pop();
    }
    
    public int top() {
        return xstk.peek();
    }
    
    public int min() {
        return minstk.peek();
    }
}

发表于 2021-02-02 09:45:07 回复(0)