【面试经典150 | 栈】最小栈

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：辅助栈
- 方法二：一个栈
- 方法三：栈中存放差值
其他语言
- python3
写在最后

Tag

【设计类】【栈】

题目来源

155. 最小栈

题目解读

本题是一个设计类的题目，设计一个最小栈类 MinStack() 实现：

MinStack()：初始化堆栈对象；
void push(int val)：将元素val推入堆栈；
void pop()：删除堆栈顶部的元素；
int top()：获取堆栈顶部的元素；
int getMin()：获取堆栈中的最小元素。

解题思路

方法一：辅助栈

维护两个栈，一个栈就是常规的栈 stk1，另一个栈 stk2 用来存放已经插入栈 stk1 中数字的最小值。

注意入栈和出栈操作时两个栈都要更新。

实现代码

class MinStack {
	
public:
	MinStack() {
		min_stk.push(INT_MAX);
	}

	void push(int val) {
		stk.push(val);
		min_stk.push(std::min(min_stk.top(), val));
	}

	void pop() {
		stk.pop();
		min_stk.pop();
	}

	int top() {
		return stk.top();
	}

	int getMin() {
		return min_stk.top();
	}

private:
	std::stack<int> stk;
	std::stack<int> min_stk;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

复杂度分析

时间复杂度： $O (1)$ 。

空间复杂度： $O (n)$ ， $n$ 为操作次数。

方法二：一个栈

可以只使用一个栈来同时保存当前的最小值和 val。

实现代码

class MinStack {
private:
    stack<pair<int, int>> stk;
public:
    MinStack() {
        stk.push(make_pair(INT_MAX, INT_MAX));
    }
    
    void push(int val) {
        stk.push({min(stk.top().first, val), val});
    }
    
    void pop() {
        stk.pop();
    }
    
    int top() {
        return stk.top().second;
    }
    
    int getMin() {
        return stk.top().first;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

复杂度分析

时间复杂度： $O (1)$ 。

空间复杂度： $O (1)$ 。

方法三：栈中存放差值

现在我们维护一个变量 minVal，表示当前插入的变量的最小值，栈中每次入栈的是 val 与 minVal 的差值 differ。现在进行具体分析：

push(int val)：如果此时栈为空，我们更新 minVal = val，向栈中插入 0；如果此时栈非空，首先向栈中插入 diff，根据 diff 的值来更新 minVal：
- 如果 diff > 0，说明插入的 val 大于当前的 minVal，则 minVal 不需要更新；
- 否则表明插入的 val 小于或者等于当前的 minVal，则更新 minVal = val。
pop()：我们需要根据 diff 来更新弹出栈顶元素后的 minVal，具体地：
- 先弹出栈顶元素 diff，并 pop；
- 如果 diff > 0，说明我们当时插入的 val 大于当时的 minVal，则 minVal 是不需要更新的；
- 否则说明当时插入的 val 小于或者等于 minVal，当时的 minVal 是插入的 val，需要将 minVal 还原回去，即当时插入 val 更新 minVal 的过程如下，还原回去得到 minVal = minVal + diff。

$d i ff = v a l - minVa l; minVa l = v a l;$

top()：如果 diff < 0，表示 minVal 就是最小栈的栈顶元素，否则 minVal + diff 才是最小栈的栈顶元素。
getMin()：直接返回 minVal 即可。

实现代码

class MinStack {
private:
    stack<long long> stk;
    long long minVal, diff;
public:
    MinStack() {
    }
    
    void push(int val) {
        if (stk.empty()) {
            stk.push(0);
            minVal = val;
        }
        else {
            diff = val - minVal;
            stk.push(diff);
            minVal = diff > 0 ? minVal : val;
        }
    }
    
    void pop() {
        diff = stk.top();
        stk.pop();
        if (diff < 0) {
            minVal = minVal - diff;
        }
    }
    
    int top() {
        return stk.top() < 0 ? minVal : minVal + stk.top();
    }
    
    int getMin() {
        return minVal;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

复杂度分析

时间复杂度： $O (1)$ 。

空间复杂度： $O (1)$ 。

其他语言

python3

以下只给出方法三的 python3 代码，该方法比较巧妙，值得好好研究。

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min_value = x
        else:
            diff = x-self.min_value
            self.stack.append(diff)
            self.min_value = self.min_value if diff > 0 else x

    def pop(self) -> None:
        if self.stack:
            diff = self.stack.pop()
            if diff < 0:
                self.min_value = self.min_value - diff

    def top(self) -> int:
        return self.min_value if self.stack[-1] < 0 else self.stack[-1] + self.min_value

    def getMin(self) -> int:
        return self.min_value if self.stack else -1