剑指offer29 JZ30 包含min函数的栈

包含min函数的栈

https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49?tpId=13&tqId=23268&ru=%2Fpractice%2F54275ddae22f475981afa2244dd448c6&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

思路

  • 首先初始化原始栈stack 和最小值栈stack_min(存储每次跟原栈中元素比较后的最小元素):

alt

  • 接下来插入(push) ‘1’这个元素,此时两个栈的变化如下图:

alt

  • 然后再插入(push) ‘2’这个元素,此时两个栈又变化如下图:

alt

  • 接着要获取栈顶元素,如下图:

alt

  • 而弹出栈顶元素,也直接调用pop函数 即可。

alt

  • 接着再次插入第三个元素 ‘1’,两个栈又发生如下变化👇:

alt ![alt]

  • 最后再次利用top函数获取到栈顶元素就变成了 1,调用min函数则获取最小值依然是 -1。

alt

代码

import java.util.Stack;

public class Solution {

    Stack<Integer> stack=new Stack<Integer>();
    //用来存贮最小元素的最小栈
    Stack<Integer>  stack_min=new Stack<Integer>();
    public void push(int node) {
        //普通栈直接放
        stack.push(node);
        //最小栈需要对比之后在放入
        //为空放入第一个元素
        if(stack_min.isEmpty()){
            stack_min.push(node);
        }
        //值比最小栈顶部元素小 直接放入最小栈
        else if(node<=stack_min.peek()){
            stack_min.push(node);
        }//值大放入自身顶部元素
            else{
                stack_min.push(stack_min.peek());
            }
    }
    
    public void pop() {
        
        stack.pop();
        stack_min.pop();
    }
    
    public int top() {
//      可以不加
//         stack_min.peek();
        return   stack.peek();
        
    }
    
    public int min() {
       return stack_min.peek();
    }
}
全部评论

相关推荐

神哥了不得:你简历字体有点不太协调呀,下面的字实在太小了呀,而且项目也不太行,建议换几个高质量的项目,面试会多很多
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务