首页 > 试题广场 >

设计getMin功能的栈

[编程题]设计getMin功能的栈

热度指数：15577 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

每次输入 [1,*] 时，表示向栈中加入数字 * ，[2] 表示移除栈顶元素，[3] 表示输入栈中最小元素，添加最小元素到结果集中即可。

数据范围：操作数 $0 \le n \le 1000000$

要求：各操作的时间复杂度 $O(1)$ ，空间复杂度 $O(n)$

示例1

输入

[[1,3],[1,2],[1,1],[3],[2],[3]]

输出

[1,2]

说明

 操作分别是：向栈push3，向栈push2，向栈push1，此时从栈底到栈顶是[3,2,1]。获得最小值，此时是1。栈pop操作，此时栈底到栈顶是[3,2]。获得最小值，此时是2。

备注:

有三种操作种类，op1表示push，op2表示pop，op3表示getMin。你需要返回和op3出现次数一样多的数组，表示每次getMin的答案

1<=操作总数<=1000000
-1000000<=每个操作数<=1000000
数据保证没有不合法的操作

算法知识视频讲解

码不停Ti2001

题目好难读懂啊

发表于 2021-03-05 16:29:20 回复(3)

青龙志

输入：[[1,3],[1,2],[1,1],[3],[2],[3]]，

返回值：[1,2]

子数组的第一个数代表操作符，1是入栈，所以3，2，1依次入栈，[3]代表getMin但不出栈，所以返回1；[2]代表出栈操作，此时1出栈；[3]再次getMin返回的就是2；整体的返回结果是两次getMin操作的结果所以是[1,2]

发表于 2021-07-03 16:11:34 回复(0)

Python

wengJJ

Python

@DaDaTheNoob的答案非常nice,这里做下笔记

堆记录数字与最小值的偏移量

data:[3,1,4,4,-1,6]

offset:[3,-2,3,3,-2,8]

可以发现offset小于0，则证明该数影响了最小值，所以pop的时候只需要检查offfset值即可

当pop出的元素是影响最小值的元素时，此时只需要利用offset修正最小值即可

#
# return a array which include all ans for op3
# @param op int整型二维数组 operator
# @return int整型一维数组
#
class Solution:
    def getMinStack(self , op ):
        # write code here
        stack = []
        result = []
        min_num = None
        offset = 0
        for i in op:
            if i[0]==1:
                if not stack:
                    min_num=i[1]
                offset = i[1]-min_num
                stack.append(offset)
                if i[1]<min_num:
                    min_num = i[1]
            elif i[0]==2:
                offset_num = stack.pop()
#                 如果偏移量小于0，证明min_num受该数影响
                if offset_num<0:
                    min_num = min_num - offset_num
            elif i[0]==3:
                result.append(min_num)
        return result

发表于 2021-04-19 18:30:05 回复(0)

breeze_blows

class Solution {
public:
    /**
     * return a array which include all ans for op3
     * @param op int整型vector<vector<>> operator
     * @return int整型vector
     */
    vector<int> getMinStack(vector<vector<int> >& op) {
        // write code here
        stack<int> s, mins;
        vector<int> res;
        for(int i = 0; i < op.size(); ++i){
            if(op[i][0] == 1){
                s.push(op[i][1]);
                if(mins.empty()){
                    mins.push(op[i][1]);
                }
                else{
                    if(mins.top() >= op[i][1]){
                        mins.push(op[i][1]);
                    }
                }
            }
            else if(op[i][0] == 2){
                int top = s.top();
                s.pop();
                if(top == mins.top()) mins.pop();
            }
            else{
                res.push_back(mins.top());
            }
        }
        return res;
    }
};

发表于 2021-03-20 11:09:25 回复(2)

肥猿

解题思路：使用两个链表来实现，

一个链表作为栈，另一个链表存储每次最小值

import java.util.*;
public class Solution {
/**
* return a array which include all ans for op3
* @param op int整型二维数组 operator
* @return int整型一维数组
*/
public int[] getMinStack (int[][] op) {
// write code here
ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0;i<op.length;i++){
if (op[i][0] == 1){ // 入栈
list.add(op[i][1]);
}else if (op[i][0] == 2){
list.remove(list.size()-1);
}else if (op[i][0] == 3)
res.add(getMin(list));
}
int [] arr = new int[res.size()];
for (int i = 0;i< res.size();i++){
arr[i] = res.get(i);
}
return arr;
}
public int getMin(ArrayList<Integer> list){
int min = Integer.MAX_VALUE;
for (int val : list){
if (min > val)
min = val;
}
return min;
}
}

发表于 2021-03-15 09:19:53 回复(0)

DaDaTheNoob

辅助栈属实不行，可以不使用额外空间完成本题目标。

核心思想：向栈中push被push的元素和当前最小值的差值，pop时还原此过程，通过栈中元素的正负来确定pop时是否需要更新当前的最小值。

时间复杂度：push: O(1), pop: O(1), get_min: O(1)

注：其他语言需要考虑int溢出问题。

class Solution:
    def __init__(self):
        self.stack = []
        self.min_num = 0

    def push(self, x: int):
        if not self.stack:
            self.min_num = x
        self.stack.append(x - self.min_num)
        if x < self.min_num:
            self.min_num = x

    def pop(self):
        p = self.stack.pop()
        if p >= 0:
            return p + self.min_num
        else:
            re = self.min_num
            self.min_num = self.min_num - p
            return re

    def get_min(self):
        return self.min_num

    def getMinStack(self , op: list[list[int]]):
        re = []
        for i in range(len(op)):
            if op[i][0] == 1:
                self.push(op[i][1])
            if op[i][0] == 2:
                self.pop()
            if op[i][0] == 3:
                re.append(self.get_min())
        return re

编辑于 2021-03-09 22:26:04 回复(0)

Newman1997

这个题关键是要理解题意，每次的输入[1，*]，表示向栈中加入数字*，而[2]表示弹出栈，[3]表示取当前栈中最小值（因此要设计一个最小值栈）

返回的是一个[***]，保存每次getMin操作的返回值，其长度和op3次数一样多

发表于 2021-03-06 22:54:02 回复(0)

BrainerGao

class Solution {
public:
    /**
     * return a array which include all ans for op3
     * @param op int整型vector<vector<>> operator
     * @return int整型vector
     */
    vector<int> getMinStack(vector<vector<int> >& op) {
        vector<int> res;
        if (op.empty()) {
            return res;
        }
        stack<int> min, s;
        for (auto p : op) {
            if (p[0] == 1) {
                s.push(p[1]);
                if (min.empty() || p[1] <= min.top()) {
                    min.push(p[1]);
                }
            } else if (p[0] == 2) {
                if (min.top() == s.top()) {
                    min.pop();
                }
                s.pop();
            } else {
                res.push_back(min.top());
            }
        }
        return res;
    }
};

发表于 2021-02-21 15:09:17 回复(0)

C/C++

Mysf

class Solution {
public:
    /**
     * return a array which include all ans for op3
     * @param op int整型vector<vector<>> operator
     * @return int整型vector
     */
    vector<int> arr; //存储值的数组
    stack<int> st;
    
    vector<int> getMinStack(vector<vector<int> >& op) {
        // 用一个栈和一个数组来实现，数组是为了维护最小值。
        if (op.size() == 0)
            return {};
        vector<int> ans;
        for (int i = 0; i < op.size(); i++) {
            if(op[i][0] == 1)
                push(op[i][1]);
            else if (op[i][0] == 2)
                pop();
            else
                ans.push_back(getmin());
        }
        return ans;
    }
    
    void push(int i) {
        st.push(i);
        arr.push_back(i);
    }
    
    void pop() {
        auto pos = find(arr.begin(), arr.end(), st.top());  //pos是迭代器类型， vector<>::iterator pos
        arr.erase(pos);
        st.pop();
    }
    
    int getmin(){
        return *min_element(arr.begin(), arr.end());
    }
};

发表于 2021-01-28 14:02:15 回复(0)

知秋一

没读懂题

发表于 2020-11-11 23:36:52 回复(19)

GryffindorIce

import java.util.*;


public class Solution {
    /**
     * return a array which include all ans for op3
     * @param op int整型二维数组 operator
     * @return int整型一维数组
     */
            // 正常的栈
    Stack<Integer> a;
        // 维护最小元素
    Stack<Integer> b;
    
    public int[] getMinStack (int[][] op) {
        // write code here
        List<Integer> res = new ArrayList<Integer>();
        a = new Stack<Integer>();
        b = new Stack<Integer>();
        
        for(int i=0;i<op.length;i++) {
            if(op[i][0] == 1) {
                push(op[i][1]);
            } else if (op[i][0] == 2) {
                pop();
            } else if(op[i][0] == 3) {
                res.add(getMin());
            } else {
                System.out.println("error");
            }

        }
        
        return res.stream().mapToInt(Integer::intValue).toArray();

    }
    
    public int pop() {
        int value = a.pop();
        // 如果pop的刚好是b的最小元素，则把此元素pop出来
        if(value == b.peek()) {
            b.pop();
        }
        return value;
    }
    
    public void push(int value) {
        a.push(value);
        // 如果b栈为空，或b的顶端大于等于此元素，一定是大于等于，因为会有重复元素
        if(b.isEmpty() || b.peek()>=value) {
            b.push(value);
        }
    }
    
    public int getMin() {
        if(b.isEmpty()) {
            return -1;
        }
        
        return b.peek();
    }
}

使用辅助栈来存最小值。

lc：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

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

牛客838877128号

题目什么意思

发表于 2021-07-03 18:07:06 回复(0)

牛客413945007号

class Solution:
    def getMinStack(self , op ):
        # write code here
        res = []
        stack = []
        for ops in op:
            if len(ops) == 2:
                if not stack:
                    stack.append(ops[1])
                else:
                    if stack[-1] <= ops[1]:
                        stack.append(stack[-1])
                    else:
                        stack.append(ops[1])
            elif ops[0] == 2:
                stack.pop()
            else:
                res.append(stack[-1])
        return res

发表于 2021-06-30 14:15:21 回复(0)

Java

牛客507555376号

import java.util.*;

class MinStack<T extends Comparable>{
    private Stack<T> stack = new Stack<>();
    private Stack<T> minStack = new Stack<>();
    public void push(T item){
        stack.push(item);
        if(minStack.isEmpty()){
            minStack.push(item);
        }else if(minStack.peek().compareTo(item)>0){
            minStack.push(item);
        }else{
            minStack.push(minStack.peek());
        }
    }
    
    public T pop(){
        minStack.pop();
        return stack.pop();
    }
    
    public T min(){
        return minStack.peek();
    }
}
public class Solution {
    /**
     * return a array which include all ans for op3
     * @param op int整型二维数组 operator
     * @return int整型一维数组
     */
    public int[] getMinStack (int[][] op) {
        if(op==null||op.length==0){
            return new int[0];
        }
        List<Integer> res = new ArrayList<>();
        MinStack<Integer> stack = new MinStack();
        for(int i=0,len=op.length;i<len;++i){
            int[] tmp = op[i];
            if(tmp[0]==1){
                stack.push(tmp[1]);
            }else if(tmp[0]==2){
                stack.pop();
            }else if(tmp[0]==3){
                res.add(stack.min());
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }
}

发表于 2021-06-04 08:24:57 回复(0)

可爱的猪

import java.util.*;

//菜鸡解法
public class Solution {
    public int[] getMinStack (int[][] op) {
        if(op==null || op.length==0 || op[0].length==0) return new int[0];
        MinStack minStack = new MinStack();
        List<Integer> ansList = new ArrayList<>();
        for(int i=0; i<op.length; i++) {
            if(op[i][0]==1) minStack.push(op[i][1]);
            else if(op[i][0]==2) minStack.pop();
            else ansList.add(minStack.getMin());
        }
        return ansList.stream().mapToInt(Integer::intValue).toArray();
    }
    
    class MinStack{
        private List<Integer> stack = new ArrayList<>();
        private List<Integer> minStack = new ArrayList<>();
        
        public void push(int num) {
            stack.add(num);
            if(minStack.isEmpty() 
               || stack.get(minStack.get(minStack.size()-1))>num) {
                minStack.add(stack.size()-1);
            }
        }
        
        public int pop() {
            if(stack.isEmpty()) return -1;
            if(minStack.get(minStack.size()-1)==stack.size()-1) 
                minStack.remove(minStack.size()-1);
            return stack.remove(stack.size()-1);
        }
        
        public int getMin() {
            if(stack.isEmpty()) return -1;
            return stack.get(minStack.get(minStack.size()-1));
        }
    }
}

发表于 2021-06-02 09:18:00 回复(0)

Rong姐姐好可爱

function getMinStack( op ) {
    // write code here
    
    // 后进先出，利用数组实现
    let temp_stack=[];
    let min=null;
    
    // 进栈
    function push(item){
        if(min>item){
            min=item;
        }
        temp_stack.push(item)
    }
    
    // 出栈
    function pop(){
        // 获取栈顶元素
        temp_stack.pop();
    }
    
    function getMin(){
        return Math.min(...temp_stack)
    }
    // 存放最小结果
    let result=[]
    // 对操作进行处理
    op.forEach(v=>{
        if(v[0]===1){
            push(v[1])
        }
        
        if(v[0]===2){
            pop()
        }
        
        if(v[0]===3){
            result.push(getMin())
        }
    })
    
    return result;
    
    
    
}

用数组来实现栈，push pop getMin操作其实很简单，就是这个题目，直接看不懂了，函数都写好了，但题目op操作没有弄懂..........

发表于 2021-05-26 15:10:49 回复(0)

C/C++

HELLOWORLDTC

class Solution {
public:
    /**
     * return a array which include all ans for op3
     * @param op int整型vector<vector<>> operator
     * @return int整型vector
     */
    vector<int> getMinStack(vector<vector<int> >& op) {
        // write code here
        int size=op.size();
        stack<int> sta;
        
        //辅助栈，只有当入主栈的值小于辅助栈的栈顶时才会压入辅助栈
        //每次对辅助栈操作需要同步更新辅助栈的栈顶，即min
        stack<int> staMin;
        int min=INT_MAX;
        vector<int> res;
        for(int i=0;i<size;i++)
        {
            //入栈操作
            if(op[i].size()==2)
            {
                if(op[i][1]<min)
                {
                    staMin.push(op[i][1]);
                    min=op[i][1];
                }
                sta.push(op[i][1]);
            }
            
            //出栈和取最小值
            else
            {
                if(op[i][0]==2)
                {
                    int temp=sta.top();
                    sta.pop();
                    if(temp==staMin.top())
                        staMin.pop();
                    
                    //每次出栈需要更新min
                    if(staMin.empty())
                        min=INT_MAX;
                    else
                    {
                        min=staMin.top();
                    }
                }
                else
                {
                    res.emplace_back(min);
                    //res.emplace_back(staMin.top());
                }
            }
        }
        return res;
    }
};

发表于 2021-05-17 23:07:31 回复(0)

害群之马

用两个栈来实现，一个栈保存数据，一个栈保存前一个栈中数据的最小值

class Solution {
public:
    /**
     * return a array which include all ans for op3
     * @param op int整型vector<vector<>> operator
     * @return int整型vector
     */
    vector<int> getMinStack(vector<vector<int> >& op) {
        // write code here
        stack<int> stk,smin;
        vector<int> res;
        for(int i=0;i<op.size();i++){
            vector<int> cmd=op[i];
            if(cmd[0]==1){
                int minv = stk.empty() ? cmd[1] :  min(cmd[1],smin.top()); 
                stk.push(cmd[1]);
                smin.push(minv);
            }
            if(cmd[0]==2){
                stk.pop();
                smin.pop();
            }
            if(cmd[0]==3){
                res.push_back(smin.top());
            }
        }
        return res;
    }
};

发表于 2021-05-08 10:30:10 回复(0)

我一定可以去实习der

import java.util.*;


public class Solution {
    /**
     * return a array which include all ans for op3
     * @param op int整型二维数组 operator
     * @return int整型一维数组
     */
    Stack<Integer> mainStcak ,supStack;
    public int[] getMinStack (int[][] op) {
        // write code here
        mainStcak = new Stack<>();
        //设置一个主栈
        supStack = new Stack<>();
        //再设置一个辅助栈
        int n = 0;
        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0 ; i < op.length ; i++){
            int[] ops = op[i];
            //push操作  辅助栈视情况push，空的时候push或者发现更小值
            if(ops[0] == 1){
                mainStcak.push(ops[1]);
                if(supStack.empty() || supStack.peek() >= ops[1]){
                    supStack.push(ops[1]);
                }
                //pop操作 如果主栈pop的就是辅助栈顶的元素，辅助栈也pop
            }else if (ops[0] == 2){
                int temp = mainStcak.pop();
                if(supStack.peek() == temp){
                    supStack.pop();
                }
            }else{
                //getmin操作
                res.add(supStack.peek());
                n++;
            }
        }
        int[] ans = new int[n];
        for(int i = 0 ; i < n ; i++){
             ans[i] = res.get(i);
        }
        return ans;
    }
}

设置个辅助栈保存min就好了

编辑于 2021-05-01 21:44:19 回复(0)

C/C++

codewind

#define is_push(x) (x==1)
#define is_pop(x) (x==2)
#define get_min(x)  (x==3)
class Solution {
public:
    /**
     * return a array which include all ans for op3
     * @param op int整型vector<vector<>> operator
     * @return int整型vector
     */
    vector<int> getMinStack(vector<vector<int> >& op) {
        // write code here
        if(op.empty()) return {};
        stack<int > stk,mins;
        vector<int > res;
        for(auto &arr: op) {
            if(is_push(arr[0])) {
                stk.push(arr[1]);
                if(mins.empty()) {
                    mins.push(arr[1]);
                }
                else if(mins.size() && mins.top() >= stk.top()) {
                     mins.push(arr[1]);
                } 
                
            }
            else if(is_pop(arr[0])) {
                if(stk.size()) {
                    if(mins.size() && stk.top() == mins.top()) mins.pop();
                    stk.pop();
                }
            }else {
                //get_min
                res.push_back(mins.top());
            }
        }
        return res;
        
        
        
    }
};

发表于 2021-04-11 16:56:39 回复(0)