包含min函数的栈

关键词：栈；双冒号

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例 1：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

解法

解法一：

思路：

将 min() 函数复杂度降为 O(1)O(1)O(1) ，可通过建立辅助栈实现；

数据栈 A ：栈 A 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。

辅助栈 B ：栈 B中存储栈 A 中所有非严格降序的元素，则栈 A 中的最小元素始终对应栈 B 的栈顶元素，即 min() 函数只需返回栈 BBB 的栈顶元素即可。

算法流程：

push(x) 函数： 重点为保持栈 B 的元素是非严格降序的。

将 x 压入栈 A （即 A.push(x) ）；
若栈 B为空或 x 小于等于栈 B 的栈顶元素，则将 x压入栈 B（即 B.push(x) ）。

pop() 函数： 重点为保持栈 A,B 的元素一致性。

执行栈 A 出栈（即 A.pop() ），将出栈元素记为 y；
若 y 等于栈 B 的栈顶元素，则执行栈 B 出栈（即 B.pop() ）。

top() 函数： 直接返回栈 A 的栈顶元素即可，即返回 A.top() 。

min() 函数： 直接返回栈 B 的栈顶元素即可，即返回 B.top() 。

代码：

class MinStack {
public:
    stack<int> stA;
    stack<int> stB;
    /** initialize your data structure here. */
    MinStack() {
        stA = {};
        stB = {};
    }
    
    void push(int x) {
        stA.push(x);
        if(stB.empty() || stB.top() >= x) stB.push(x);
    }
    
    void pop() {
        if(stA.top() == stB.top()) stB.pop();
        stA.pop();
    }
    
    int top() {
        return stA.top();
    }
    
    int min() {
        return stB.top();
    }
};

代码二：

class MinStack {
public:
    /** initialize your data structure here. */
    stack<long long> data, min_d;
    
    MinStack() {
    }
    
    void push(int x) {
        data.push(x);
        min_d.push(min_d.empty() ? x : ::min(min_d.top(), (long long)x));
        //::min因为类里面有一个min函数，直接使用min的话会调用类中的函数，加上::后调用的是全局的min函数。
    }
    
    void pop() {
        data.pop();
        min_d.pop();//因为min_d和data一样，一直在push
    }
    
    int top() {
        return data.top();
    }
    
    int min() {
        return min_d.top();
    }
};

包含min函数的栈

scorlw 发布于 2020-06-21

包含min函数的栈

题目描述

解法

解法一：

知识点