leetcode155：最小栈

题目链接

leetcode

题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

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

C++ 代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

/*
    两个栈：一个存放元素，一个存放最小值。

    时间复杂度：O(1)
        push、pop、top、getMin 操作都是 O(1)，每个操作最多调用栈操作两次。
    空间复杂度：O(n)
        其中 n 为总操作数。
        最坏情况下，连续插入 n 个元素，两个栈占用的空间为 O(n)。
*/
class MinStack {
public:
    MinStack() {
        minStack.push(INT_MAX);
    }
    
    void push(int val) {
        numStack.push(val);
        minStack.push(min(minStack.top(), val));
    }
    
    void pop() {
        numStack.pop();
        minStack.pop();
    }
    
    int top() {
        return numStack.top();
    }
    
    int getMin() {
        return minStack.top();
    }

private:
    stack<int> numStack;
    stack<int> minStack;
};

/*
    一个栈，栈中存放当前元素与当前最小值的差值。
    一个变量 minVal，记录最小值

    进栈
        如果栈为空，则插入当前元素，更新 minVal；
        如果栈不空，则插入 x-minVal，更新 minVal。
    出栈
        如果栈顶元素小于 0，则说明栈顶元素为当前最小值，需要回滚上一次的最小值。
    取栈顶元素
        如果栈中只有一个元素，直接返回；
        如果栈顶元素大于 0，则说明栈顶不是当前最小值，通过差值计算找到最小值；
        如果栈顶元素小于 0，则直接返回最小值。
    返回最小值
        直接返回 minVal

    时间复杂度：O(1)
       push、pop、top、getMin 操作都是 O(1)。
    空间复杂度：O(n)
        其中 n 为总操作数。
        最坏情况下，连续插入 n 个元素，栈占用的空间为 O(n)。
*/
class MinStack_1 {
public:
    MinStack_1() {

    }
    
    void push(int val) {
        if (stk.empty()) {
            stk.push(val);
            minVal = val;
        } else {
            stk.push(val-minVal);
            minVal = min(minVal, (long long) val);
        }
    }
    
    void pop() {
        if (stk.top() < 0) {
            minVal -= stk.top();
        }
        stk.pop();
    }
    
    int top() {
        if (stk.size() == 1) {
            return stk.top();
        } else if (stk.top() > 0) {
            return minVal + stk.top();
        }
        return minVal;
    }
    
    int getMin() {
        return minVal;
    }

private:
    stack<long long> stk;
    long long minVal;
};

// 辅助函数：打印数组
void printArray(const vector<string>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "\"" << nums[i] << "\"";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    MinStack minStack;
    vector<string> operations = {"MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"};
    vector<vector<int>> params = {{}, {-2}, {0}, {-3}, {}, {}, {}, {}};
    vector<string> output;

    for (int i = 0; i < operations.size(); i++) {
        string op = operations[i];
        if (operations[i] == "MinStack") {
            // 初始化 MinStack 实例，不进行任何操作，不返回值
            output.push_back("null");
        } else if (operations[i] == "push") {
            minStack.push(params[i][0]);
            output.push_back("null"); // 执行了 push 操作，不返回具体值
        } else if (operations[i] == "pop") {
            minStack.pop();
            output.push_back("null"); // 执行了 pop 操作，不返回具体值
        } else if (operations[i] == "top") {
            int top = minStack.top();
            output.push_back(to_string(top));
        } else if (operations[i] == "getMin") {
            int min = minStack.getMin();
            output.push_back(to_string(min));
        }
    }

    cout << "Input: " << endl;
    printArray(operations);
    cout << endl;
    printArray(params);
    cout << endl;
    cout << "Output: " << endl;
    printArray(output);
    cout << endl;

    return 0;
}