剑指 Offer 30. 包含min函数的栈

忘是亡心i 2024-03-23 14:18 29阅读 0赞

#### 目录 ####

*   *  题目思路
     *  代码实现

题目来源  
[剑指 Offer 30. 包含min函数的栈][Offer 30. _min]

### 题目思路 ###

**push(x) 函数：** 重点为保持栈 B的元素是 非严格降序 的。

*  将 x 压入栈 A （即 A.push(x) ）；
 *  若 栈 B 为空 或 x 小于等于 栈 B 的栈顶元素，则将 x 压入栈 B （即 B.push(x) ）。

**pop() 函数：** 重点为保持栈 A,B 的 元素一致性 。

*  执行栈 A 出栈（即 A.pop() ），将出栈元素记为 y ；
 *  若 y 等于栈 B 的栈顶元素，则执行栈 B 出栈（即 B.pop() ）。

**top() 函数：** 直接返回栈 A 的栈顶元素即可，即返回 A.peek() 。

**min() 函数：** 直接返回栈 B 的栈顶元素即可，即返回 B.peek() 。  
![在这里插入图片描述][a03c64afa67a4f47b1f9cb7e7ac54d73.png]

### 代码实现 ###

class MinStack {
        
    
        /** initialize your data structure here. */
        Stack<Integer> A;
        Stack<Integer> B;
    
        public MinStack() {
        
            A = new Stack<Integer>();
            B = new Stack<Integer>();
        }
        
        public void push(int x) {
        
            A.push(x);
            if(B.empty() || B.peek() >= x)
                B.add(x);
        }
        
        public void pop() {
        
            if(A.pop().equals(B.peek())){
        
                B.pop();
            }
            
    
        }
        
        public int top() {
        
            return A.peek();
        }
        
        public int min() {
        
            return B.peek();
    
        }
    }
    
    /**
     * 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.min();
     */

![在这里插入图片描述][3d9183abcc004a4bbad91a5f28f16b25.png]

[Offer 30. _min]: https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/
[a03c64afa67a4f47b1f9cb7e7ac54d73.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9cea2536b8be4de5a99c16e5472fe26d.png
[3d9183abcc004a4bbad91a5f28f16b25.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/e097afb8923840fea511a85b48adc835.png