项目简介

这个项目展示了100道经典LeetCode算法题在实际工程中的应用场景，帮助学员理解算法的实用价值，建立理论与实践的桥梁。

核心目标

• 让算法学习更有意义，不再是纸上谈兵

• 帮助面试者理解算法背后的工程价值

• 为工程师提供算法选择的实际参考

这是栈/队列应用的第七篇：最小栈实现

视频讲解与源码领取：你不光要刷力扣，还要懂力扣算法100个实际使用场景(上)

实际应用

在数据库查询优化、编译器优化、游戏AI决策中，经常需要维护一个栈结构，同时能够快速获取当前栈中的最小值。这在回溯算法、状态管理、性能监控等场景中非常有用。

最小栈结构示意图

对应算法

LeetCode题目: 155. 最小栈

核心思想:

LeetCode 155要求设计一个栈，支持push、pop、top和getMin操作，且所有操作都是O(1)时间复杂度。解决方案使用辅助栈来维护最小值：

1. 双栈设计: 主栈存储所有元素，辅助栈存储每个状态下的最小值

2. 同步操作: push时同时更新两个栈，pop时同时弹出

3. 最小值维护: 辅助栈顶始终保持当前主栈的最小值

4. 空间优化: 可以只在需要时才向辅助栈添加元素

算法精髓:

通过空间换时间，用额外的栈空间来维护最小值信息，实现O(1)的最小值查询。

应用领域

1. 股票交易系统 - 实时维护当前时间窗口内的最低价格

2. 游戏排行榜 - 维护玩家分数历史的最低点

3. 系统监控 - 跟踪服务器性能指标的最小值

代码示例

// 最小栈的高级实现 - 支持多种优化策略
class MinStack {
private:
    struct StackNode {
        int value;
        int min_value;  // 到当前位置为止的最小值
        
        StackNode(int val, int min_val) : value(val), min_value(min_val) {}
    };
    
    stack<StackNode> main_stack;
    
public:
    /**
     * @brief 压入元素
     * @param x 要压入的值
     */
    void push(int x) {
        // 计算新的最小值
        int new_min = main_stack.empty() ? x : min(x, main_stack.top().min_value);
        
        // 压入新节点
        main_stack.push(StackNode(x, new_min));
        
        cout << "压入 " << x << "，当前最小值: " << new_min << endl;
    }
    
    /**
     * @brief 弹出栈顶元素
     */
    void pop() {
        if (main_stack.empty()) {
            cout << "栈为空，无法弹出" << endl;
            return;
        }
        
        int popped_value = main_stack.top().value;
        main_stack.pop();
        
        cout << "弹出 " << popped_value;
        if (!main_stack.empty()) {
            cout << "，当前最小值: " << main_stack.top().min_value;
        } else {
            cout << "，栈已空";
        }
        cout << endl;
    }
    
    /**
     * @brief 获取栈顶元素
     * @return 栈顶元素值
     */
    int top() {
        if (main_stack.empty()) {
            throw runtime_error("栈为空");
        }
        return main_stack.top().value;
    }
    
    /**
     * @brief 获取栈中最小元素
     * @return 最小元素值
     */
    int getMin() {
        if (main_stack.empty()) {
            throw runtime_error("栈为空");
        }
        return main_stack.top().min_value;
    }
    
    /**
     * @brief 获取栈的大小
     */
    int size() const {
        return main_stack.size();
    }
    
    /**
     * @brief 检查栈是否为空
     */
    bool empty() const {
        return main_stack.empty();
    }
    
    /**
     * @brief 打印栈的详细状态
     */
    void printStack() {
        if (main_stack.empty()) {
            cout << "栈为空" << endl;
            return;
        }
        
        cout << "=== 栈状态 ===" << endl;
        stack<StackNode> temp = main_stack;
        vector<StackNode> nodes;
        
        // 将所有元素取出
        while (!temp.empty()) {
            nodes.push_back(temp.top());
            temp.pop();
        }
        
        // 从栈顶到栈底打印
        cout << "位置  值   最小值" << endl;
        for (int i = nodes.size() - 1; i >= 0; --i) {
            cout << setw(3) << (nodes.size() - i) << "  " 
                 << setw(3) << nodes[i].value << "  " 
                 << setw(6) << nodes[i].min_value << endl;
        }
        cout << "==============" << endl;
    }
};

// 空间优化版本的最小栈
class OptimizedMinStack {
private:
    stack<int> main_stack;
    stack<int> min_stack;  // 只存储真正的最小值变化点
    
public:
    void push(int x) {
        main_stack.push(x);
        
        // 只有当新值小于等于当前最小值时，才压入最小值栈
        if (min_stack.empty() || x <= min_stack.top()) {
            min_stack.push(x);
        }
    }
    
    void pop() {
        if (main_stack.empty()) return;
        
        int popped = main_stack.top();
        main_stack.pop();
        
        // 如果弹出的是最小值，也要从最小值栈中弹出
        if (!min_stack.empty() && popped == min_stack.top()) {
            min_stack.pop();
        }
    }
    
    int top() {
        return main_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
    
    /**
     * @brief 获取空间使用效率
     * @return 最小值栈的空间占用比例
     */
    double getSpaceEfficiency() {
        if (main_stack.empty()) return 0.0;
        return (double)min_stack.size() / main_stack.size();
    }
};

// 应用示例：股票价格监控
class StockPriceMonitor {
private:
    MinStack price_history;
    string stock_symbol;
    
public:
    StockPriceMonitor(const string& symbol) : stock_symbol(symbol) {}
    
    /**
     * @brief 记录新的股票价格
     * @param price 股票价格（以分为单位避免浮点数问题）
     */
    void recordPrice(int price) {
        price_history.push(price);
        cout << stock_symbol << " 新价格: " << (price / 100.0) 
             << " 元，历史最低: " << (price_history.getMin() / 100.0) << " 元" << endl;
    }
    
    /**
     * @brief 获取当前价格
     */
    double getCurrentPrice() {
        return price_history.top() / 100.0;
    }
    
    /**
     * @brief 获取历史最低价
     */
    double getLowestPrice() {
        return price_history.getMin() / 100.0;
    }
    
    /**
     * @brief 检查是否创造了新低
     */
    bool isNewLow() {
        return price_history.top() == price_history.getMin();
    }
    
    /**
     * @brief 生成价格报告
     */
    void generateReport() {
        cout << "\n=== " << stock_symbol << " 价格报告 ===" << endl;
        cout << "当前价格: " << getCurrentPrice() << " 元" << endl;
        cout << "历史最低: " << getLowestPrice() << " 元" << endl;
        cout << "价格记录数: " << price_history.size() << endl;
        if (isNewLow()) {
            cout << "🔻 当前价格为历史新低！" << endl;
        }
        cout << "============================" << endl;
    }
};