 检索))
LeetCode 155. 最小栈
📌 题目描述
题目级别：中等
设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。
实现MinStack类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
💡 破题思路：状态打包法 (Pair)
题目要求在O(1)O(1)O(1)的时间内获取栈中的最小元素。
由于栈的特性是后进先出（LIFO），这意味着：在任何一个元素被压入栈的瞬间，从栈底到它这个位置的“最小元素”其实就已经确定了，且只要它不出栈，这个最小值永远不会变！
常见的解法是维护两个平行的栈（一个存数据，一个存最小值）。但更优雅、更极客的解法是：将数据和它入栈那一刻的最小值“打包”在一起！
在 C++ 中，我们可以使用std::pair完美实现这一点。
定义stack<pair<int, int>> st;
pair.first存储真实的元素值val。pair.second存储该元素入栈时的历史最小值min_val。
推导过程：
每次push时，我们将当前值与原栈顶的min_val比较，取较小者，和当前值一起打包压入栈中。
每次pop时，直接连同值和附带的最小值一起弹出，完美恢复上一个状态。不需要任何复杂的同步逻辑！
💻 C++ 代码实现 (极简 Pair 法)
classMinStack{public:// pair 的 first 存实际值，second 存截止到当前的最小值stack<pair<int,int>>st;MinStack(){}voidpush(intval){// 如果栈为空，当前值就是最小值if(st.empty()){st.push({val,val});}else{// 如果栈不为空，将当前值与栈顶记录的最小值进行比较st.push({val,min(val,st.top().second)});}}voidpop(){// 弹出数据的同时，也弹出了它对应的最小值状态，自然恢复到上一个状态st.pop();}inttop(){returnst.top().first;}intgetMin(){returnst.top().second;}};/** * 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(); */
