155-最小栈/最大栈

LeetCode 155. Min Stack

LeetCode-155

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top()gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 $O(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.

method: 栈

用两个栈，一个stackValue存储每个数值，一个stackMin作单调栈，从栈底到栈顶单调递减

如果后面的数比当前的最小值大，那么他一定会先弹出，所以没必要入单调栈
比如，1 2 3分别入栈stackValue
1入栈stackMin，2和3不用，因为2和3肯定会在1之前出栈stackValue，在此期间最小值一直是1

class MinStack {
public:
    stack<int> stackValue;
    stack<int> stackMin;
    MinStack() {}
    
    void push(int x) {
        stackValue.push(x);
        if (stackMin.empty() || x <= stackMin.top())    // 等于也要压栈
            stackMin.push(x);
    }
    
    void pop() {
        int x = stackValue.top();
        stackValue.pop();
        if (x == stackMin.top()) stackMin.pop();
    }
    
    int top() {
        return stackValue.top();
    }
    
    int getMin() {
        return stackMin.top();
    }
};

---

LeetCode 716. 最大栈

设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。

实现 MaxStack 类：

MaxStack() 初始化栈对象
void push(int x) 将元素 x 压入栈中。
int pop() 移除栈顶元素并返回这个元素。
int top() 返回栈顶元素，无需移除。
int peekMax() 检索并返回栈中最大元素，无需移除。
int popMax() 检索并返回栈中最大元素，并将其移除。如果有多个最大元素，只要移除 最靠近栈顶 的那个。

示例：

输入
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
输出
[null, null, null, null, 5, 5, 1, 5, 1, 5]

解释
MaxStack stk = new MaxStack();
stk.push(5);   // [5] - 5 既是栈顶元素，也是最大元素
stk.push(1);   // [5, 1] - 栈顶元素是 1，最大元素是 5
stk.push(5);   // [5, 1, 5] - 5 既是栈顶元素，也是最大元素
stk.top();     // 返回 5，[5, 1, 5] - 栈没有改变
stk.popMax();  // 返回 5，[5, 1] - 栈发生改变，栈顶元素不再是最大元素
stk.top();     // 返回 1，[5, 1] - 栈没有改变
stk.peekMax(); // 返回 5，[5, 1] - 栈没有改变
stk.pop();     // 返回 1，[5] - 此操作后，5 既是栈顶元素，也是最大元素
stk.top();     // 返回 5，[5] - 栈没有改变

method

入队的时候，看要入队的元素是否比当前最大值大，如果较大，则stMax需要插入这个数，否则，stMax插入当前的栈顶元素

弹出最大值的时候，stMax.top()记录着最大值Max，先把stVal中不等于Max的元素放到一个临时的栈中，等找到stVal中等于Max的元素时，先把这个元素弹出，再将临时栈中的元素插入回去，注意这里调用的是前面实现的自定义的push

class MaxStack {
public:
    stack<int> stVal;
    stack<int> stMax;
    MaxStack() {}
    
    void push(int x) {
        stVal.push(x);
        int max = stMax.empty() ? x : stMax.top();
        stMax.push(max > x ? max : x);  // 插入较大的
    }
    
    int pop() {
        int x = stVal.top();
        stVal.pop();
        stMax.pop();
        return x;
    }
    
    int top() {
        return stVal.top();
    }
    
    int peekMax() {
        return stMax.top();
    }
    
    int popMax() {
        stack<int> tmp;
        int x = stMax.top();
        while (stVal.top() != x) {
            tmp.push(stVal.top());
            stVal.pop();
            stMax.pop();
        }
        stVal.pop();
        stMax.pop();
        while (!tmp.empty()) {
            this->push(tmp.top());  // 这里调用前面自定义的push
            tmp.pop();
        }
        return x;
    }
};