列表

详情


BM43. 包含min函数的栈

描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的 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

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C 解法, 执行用时: 2ms, 内存消耗: 476KB, 提交时间: 2022-01-25

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param value int整型 
 * @return 无
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
static int stack[310];
static int i=0;
static int min_num=99999;
void push(int value ) {
    stack[i++]=value;
}

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return 无
 */
void pop() {
    i--;
}

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return int整型
 */
int top() {
    int top_num=stack[--i];
    i++;
    return top_num;
}

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param 无 
 * @return int整型
 */
int min() {
    int min;
    for(int k=0;k<i;k++)
    {
        if(stack[k]<min_num)
        {
            min_num=stack[k];
        }
    }
    min=min_num;
    min_num=99999;
    return min;
}


C++ 解法, 执行用时: 2ms, 内存消耗: 524KB, 提交时间: 2022-02-09

class Solution
{
public:
    void push(int value)
    {
        s_.push_back(value);
    }
    void pop()
    {
        s_.erase(--s_.end());

    }
    int top()
    {
        return *(--s_.end());
    }
    int min()
    {
        int min = 0x7fffffff;
        for (auto i : s_)
        {
            if (i < min)
                min = i;
        }
        return min;
    }

private:
    vector<int> s_;
};

C++ 解法, 执行用时: 2ms, 内存消耗: 544KB, 提交时间: 2022-03-12

 class Solution {
public:
        vector<int>stack;//看了答案才知道还能加入vector 以为不能变化
    void push(int value) {
        stack.push_back(value);
    }
    void pop() {
        if(!stack.empty())
        stack.pop_back();
    }
    int top() {
        return stack[stack.size() - 1];
    }
    int min() {
        int i = stack.size()-1;
        int Min = stack[i];
        i--;
        while (i+1) {
            if (stack[i] < Min)
                Min = stack[i];
            i--;
        }
        return Min;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 544KB, 提交时间: 2022-01-25

class Solution {
private:
    stack<pair<int, int>> stk;
    
public:
    void push(int value) {
        if (stk.empty()) {
            stk.emplace(value, value);
            return ;
        }
        
        stk.emplace(value, std::min(stk.top().second, value));
    }
    void pop() {
        stk.pop();
    }
    int top() {
        return stk.top().first;
    }
    int min() {
        return stk.top().second;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 556KB, 提交时间: 2022-02-10

class Solution {
public:
    stack<int> stk;
    stack<int> minStk;
    Solution(){
        minStk.push(INT_MAX);
    }
    void push(int value) {
        stk.push(value);
        if(value < minStk.top()){
            minStk.push(value);
        } else {
            minStk.push(minStk.top());
        }
    }
    void pop() {
        stk.pop();
        minStk.pop();
    }
    int top() {
        return stk.top();
    }
    int min() {
        return minStk.top();
    }
};

上一题