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