LeetCode 155. 最小栈 | C++语言版

LeetCode 155. 最小栈 | C++语言版

LeetCode 155. 最小栈

题目描述

题目地址：155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

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

解题思路

思路一：使用辅助栈

代码实现

C++

classMinStack{//#define INT_MAX 100public://定义两个栈容器//首先定义一个 「数据栈」来支持常规的 push、pop、top 操作
    stack<int> st;//再定义一个「辅助栈」，其栈顶一直保持为当前的最小值，以支持常数时间复杂度的 getMin 操作
    stack<int> minStack;//构造函数清空栈容器MinStack(){while(!st.empty()) st.pop();while(!minStack.empty()) minStack.pop();//初始化最小栈的栈顶元素为最大值,防止top访问空指针报错
        minStack.push(INT_MAX);}voidpush(int val){
        st.push(val);//比较最小栈的栈顶的值和当前值val的大小，将最小值押入最小栈
        minStack.push(min(minStack.top(),val));}voidpop(){//弹出两个栈的栈顶元素
        st.pop();
        minStack.pop();}inttop(){return st.top();}intgetMin(){//当前最小栈的栈顶元素就是此时st栈的最小值return minStack.top();}};/**
 * 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();
 */

在这里插入代码片

运行结果

参考文章：

https://leetcode.cn/problems/min-stack/solutions/1373944/by-nehzil-uofk/
https://leetcode.cn/problems/min-stack/solutions/243226/3-chong-fang-fa-shi-xian-bi-xu-miao-dong-by-sweeti/

思路二：减少遍历节点数

代码实现

在这里插入代码片

运行结果

参考文章：