文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接155.最小栈2、题目描述二、个人思路整理1、思路分析核心思路维护两个栈主数据栈st正常存放所有压入的元素。辅助最小栈min_st栈顶始终保存当前主栈中的最小值。操作逻辑push(val)st.push(val)。若min_st为空或val min_st.top()将val也压入min_st注意带有重复出现的最小值也要入栈。pop()如果st.top() min_st.top()说明弹出的正是当前最小值min_st.pop()需同步执行。st.pop()。top()返回st.top()。getMin()直接返回min_st.top()。2、解题代码classMinStack{private:stackintst;// 主数据栈按常规顺序存放所有压入的元素stackintmin_st;// 辅助最小栈栈顶始终记录当前主栈内的最小值public:MinStack(){}voidpush(intvalue){st.push(value);// 若辅助栈为空或新值小于等于当前最小值则压入辅助栈// 注意此处必须使用 确保重复出现的最小值能够正确维护计数与状态if(min_st.empty()||valuemin_st.top()){min_st.push(value);}}voidpop(){// 若主栈弹出的元素与辅助栈相同说明弹出了当前最小值辅助栈需同步出栈if(st.top()min_st.top()){min_st.pop();}st.pop();}inttop(){// 直接返回主栈栈顶元素时间复杂度 O(1)returnst.top();}intgetMin(){// 辅助栈顶即为当前所有元素的最小值时间复杂度 O(1)returnmin_st.top();}};/** * Your MinStack object will be instantiated and called as such: * MinStack* obj new MinStack(); * obj-push(value); * obj-pop(); * int param_3 obj-top(); * int param_4 obj-getMin(); */复杂度分析时间复杂度push(val)O ( 1 ) O(1)O(1)常数次栈操作。pop()O ( 1 ) O(1)O(1)仅对比栈顶并弹出元素。top()O ( 1 ) O(1)O(1)直接读取主栈栈顶。getMin()O ( 1 ) O(1)O(1)直接读取辅助栈栈顶。各项操作的时间复杂度均为O ( 1 ) O(1)O(1)。空间复杂度O ( n ) O(n)O(n)。设当前栈内元素总数为n nn。主栈 st 需要存储所有n nn个元素O ( n ) O(n)O(n)辅助栈 min_st 在单调递减入栈的最坏情况下最多存储n nn个元素O ( n ) O(n)O(n)因此额外辅助空间与整体空间开销均为O ( n ) O(n)O(n)。三、知识风暴辅助栈Auxiliary Stack是本题的核心思想。它通过额外维护一个栈来记录当前状态下的最值信息从而在O ( 1 ) O(1)O(1)时间内完成查询。理解辅助栈的同步更新规则与边界条件对掌握本题至关重要。算法核心思想空间换时间主栈st负责常规存储辅助栈min_st专门记录历史最小值。通过牺牲O ( n ) O(n)O(n)的辅助空间换取所有操作O ( 1 ) O(1)O(1)的时间复杂度。同步维护本质每次push时若新值不大于当前最小值则同步压入辅助栈每次pop时若弹出的正是当前最小值则同步弹出。辅助栈与主栈始终保持「栈顶即当前最小值」的对应关系。比较基准的选择本题的关键技巧是使用而非。当重复最小值出现时必须将其一并压入辅助栈否则后续pop会因计数错乱而丢失最小值信息。常见对比辅助栈 vs 暴力查询辅助栈Auxiliary Stack用额外栈顶记录最值每次操作仅常数次栈操作时间复杂度O ( 1 ) O(1)O(1)适合频繁查询最值的场景。暴力查询线性扫描每次getMin()都遍历整个主栈找最小值时间复杂度O ( n ) O(n)O(n)实现简单但效率低无法满足本题对O ( 1 ) O(1)O(1)的要求。共同点两者都能正确返回最小值。区别在于辅助栈用空间换时间、每次查询都是常数时间而暴力查询不占额外空间、但代价是线性时间。“同步更新”定义思想核心思想辅助栈的生命周期必须与主栈严格同步——入栈时按规则记录出栈时按规则清除保证任意时刻辅助栈顶都准确反映当前主栈的最小值。与本题的联系push时若val min_st.top()则入辅助栈pop时若st.top() min_st.top()则辅助栈同步弹出。两条规则共同保证「辅助栈顶 当前最小值」这一不变量始终成立。注意事项pop时不能只弹主栈而忽略辅助栈。若弹出的恰是最小值而辅助栈未同步弹出则辅助栈顶会残留已不存在的旧最小值导致后续getMin()返回错误结果。使用要点入栈判定min_st.empty() || val min_st.top()时压入辅助栈。empty()判断保证首个元素必然入栈保证重复最小值被正确计数。出栈判定st.top() min_st.top()时辅助栈同步弹出。只有弹出的是当前最小值才需要同步否则辅助栈保持不变。查询操作top()直接返回st.top()getMin()直接返回min_st.top()两者均为O ( 1 ) O(1)O(1)常数时间。不变量验证任意操作序列结束后辅助栈顶始终等于主栈当前所有元素的最小值这是整个算法正确性的根基。算法变体与扩展最大栈Max Stack与最小栈对称辅助栈记录最大值push时用判定是辅助栈思想的直接推广。双端队列维护滑动窗口最值LeetCode 239用单调双端队列在O ( n ) O(n)O(n)内求滑动窗口最大值体现「额外数据结构维护最值」思想的进阶应用。用队列实现栈 / 用栈实现队列LeetCode 225 / 232用两个栈或两个队列互相配合模拟另一种数据结构是「辅助结构 主结构」组合思想的经典变体。单调栈Monotonic Stack维护栈内元素单调递增或递减常用于解决「下一个更大元素」等问题是辅助栈思想在更复杂场景下的延伸。相关 LeetCode 例题225. 用队列实现栈辅助结构 主结构配合232. 用栈实现队列辅助结构 主结构配合239. 滑动窗口最大值单调队列维护最值496. 下一个更大元素 I单调栈 哈希映射