AcWing 41. 包含min函数的栈

红太狼 2023-01-11 09:19 84阅读 0赞

**上一篇博客：[AcWing 20. 用两个栈实现队列][AcWing 20.]**

>  写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[AcWing 41. 包含min函数的栈][AcWing 41. _min]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  样例
 *  题解
 *   *  解题思路
     *  写法一
     *  写法二

# 题目信息 #

## 题目描述 ##

设计一个支持push，pop，top等操作并且可以在 `O(1)` 时间内检索出最小元素的堆栈。

*  push(x)–将元素x插入栈中
 *  pop()–移除栈顶元素
 *  top()–得到栈顶元素
 *  getMin()–得到栈中最小元素

## 样例 ##

> MinStack minStack = new MinStack();  
> minStack.push(-1);  
> minStack.push(3);  
> minStack.push(-4);  
> minStack.getMin(); --> Returns -4.  
> minStack.pop();  
> minStack.top(); --> Returns 3.  
> minStack.getMin(); --> Returns -1.

# 题解 #

## 解题思路 ##

使用两个栈，栈 `stk` 用来正常的存储数据，栈 `min_stk` 用来维护当前栈中最小的元素，使 `min_stk` 的栈顶始终保存最小的元素。这样每当我们需要获取最小元素时，直接return `min_stk` 的栈顶元素即可。弹出元素时同时弹出两个栈的栈顶元素即可。主要问题在于 `min_stk` 的push操作。第一种方法是我自己想的，第二种是Y总的写法。两种方法都可以 AC，但是自己的想法比较麻烦，不如Y总的简洁深刻。

**push()方法一：**  
  `stk`每次push进一个元素都比较一下当前元素和 `min_stk` 栈顶元素的大小，如果 `min_stk` 为空那么直接将该元素push到 `min_stk` 中，如果比 `min_stk` 的栈顶元素小，那么就将该数push到 `min_stk` 中，否则就将 `min_stk` 的栈顶元素再push一次。

**push()方法二：**  
 先判断一下 `min_stk` 中是否有元素，如果有那么就比较一下新元素和当前栈顶元素的大小，再将小的元素push到 `min_stk` 中。如果 `min_stk` 中没有元素直接将新元素push进去。

## 写法一 ##

class MinStack { 
    public:
        stack<int> stk, min_stk;
        /** initialize your data structure here. */
        MinStack() { 
            
        }
        
        void push(int x) { 
            stk.push(x);
            if (min_stk.empty()) min_stk.push(x);
            else if (x < min_stk.top()) { 
                min_stk.push(x);
            } else { 
                min_stk.push(min_stk.top());
            }
        }
        
        void pop() { 
            stk.pop();
            min_stk.pop();
        }
        
        int top() { 
            return stk.top();
        }
        
        int getMin() { 
            return min_stk.top();
        }
    };
    
    /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

## 写法二 ##

class MinStack { 
    public:
       stack<int> stk, min_stk;
       /** initialize your data structure here. */
       MinStack() { 
           
       }
       
       void push(int x) { 
           stk.push(x);
           if (min_stk.size()) x = min(x, min_stk.top());
           min_stk.push(x);
       }
       
       void pop() { 
           stk.pop();
           min_stk.pop();
       }
       
       int top() { 
           return stk.top();
       }
       
       int getMin() { 
           return min_stk.top();
       }
    };
    
    /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

--------------------

> 未完待续，持续更新中……  
> ![20210126190124230.png][]

[AcWing 20.]: https://ac-fun.blog.csdn.net/article/details/113141893
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[AcWing 41. _min]: https://www.acwing.com/problem/content/description/90/
[20210126190124230.png]: /images/20221119/677c3c738a4e4a74b2b6649c9cf4afdb.png