【面试算法】一个有getMin功能的栈

he_xd 发布于2019-08-14 15:17 / 1880人阅读

摘要：题目实现一个特殊的栈，在实现栈的基本功能上再实现一个实现返回栈中最小元素的操作。要求，操作的时间复杂度都是，设计的栈类型额可以使用现成的栈结构。第一种代码实现第二种代码实现

【题目】实现一个特殊的栈，在实现栈的基本功能上再实现一个实现返回栈中最小元素的操作。
【要求】
1，pop、push、getMin操作的时间复杂度都是O（1）；
2，设计的栈类型额可以使用现成的栈结构。

第一种代码实现：

public class GetMinStack_1 {

    private Stack stackData;
    private Stack stackMin;

    public GetMinStack_1(){
        stackData = new Stack();
        stackMin = new Stack();
    }

    public void push(int newNum){
        if (stackMin.isEmpty()) {
            stackMin.push(newNum);
        }else if (newNum <= getMin()) {
            stackMin.push(newNum);
        }
        stackData.push(newNum);
    }

    public int pop(){
        if (stackData.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        int value = stackData.pop();
        if (value == getMin()) {
            stackMin.pop();
        }
        return value;
    }

    private int getMin() {
        // TODO Auto-generated method stub
        if (stackMin.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        return stackMin.peek();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        GetMinStack_1 stack = new GetMinStack_1();
        int[] testNum = {4,2,4,6,5,0,1,10};
        for(int i:testNum){
            stack.push(i);
        }
        for(int i = 0; i < testNum.length; i++){
            System.out.println(stack.getMin()+" "+stack.pop());
        }
    }

}

第二种代码实现：

public class GetMinStack_2 {

    private Stack stackData;
    private Stack stackMin;

    public GetMinStack_2(){
        stackData = new Stack();
        stackMin = new Stack();
    }

    public void push(int newNum){
        if (stackMin.isEmpty()) {
            stackMin.push(newNum);
        }
        else if (newNum <= getMin()) {
            stackMin.push(newNum);
        }else {
            stackMin.push(getMin());
        }
        stackData.push(newNum);
    }

    public int pop(){
        if (stackData.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        int value = stackData.pop();
        stackMin.pop();
        return value;
    }

    private int getMin() {
        // TODO Auto-generated method stub
        if (stackMin.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        return stackMin.peek();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        GetMinStack_2 stack = new GetMinStack_2();
        int[] testNum = {4,2,4,6,5,0,1,10};
        for(int i:testNum){
            stack.push(i);
        }
        for(int i = 0; i < testNum.length; i++){
            System.out.println(stack.getMin()+" "+stack.pop());
        }
    }
}

云服务器 GPU云服务器面试一个php 自然语言处理算法面试字符串算法面试题面试c语言算法编程题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65579.html

【刷算法】LeetCode.155-最小栈

摘要：题目描述设计一个支持，，操作，并能在常数时间内检索到最小元素的栈。删除栈顶的元素。检索栈中的最小元素。示例返回返回返回代码实现题目描述设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。示例...

wing324 2019-08-23 11:31 评论0 收藏0
LeetCode 155：最小栈 Min Stack

摘要：删除栈顶的元素。可以另外新建一个栈来顺序存入数据最小值。另外在数据入栈时需要判断该值是否比辅助栈的栈顶元素的值更小，如果更小，也应该将它加入辅助栈。并且需要判断辅助栈是否为空，在不空的条件下才可以取栈顶元素比较，否则会溢出。 LeetCode 155：最小栈 Min Stack 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) -- ...

LeexMuller 2019-08-19 10:16 评论0 收藏0
【Java】几道常见的秋招面试题

摘要：总结的时间复杂度是，是空间是使用辅助栈来存储最小值。项目就是为了解决配置繁琐的问题，最大化的实现约定大于配置。前言只有光头才能变强 Redis目前还在看，今天来分享一下我在秋招看过(遇到)的一些面试题(相对比较常见的) 0、final关键字简要说一下final关键字，final可以用来修饰什么？这题我是在真实的面试中遇到的，当时答得不太好，现在来整理一下吧。 final可以修饰...

Rocko 2019-08-16 13:29 评论0 收藏0
力扣(LeetCode)155

摘要：题目地址题目描述设计一个支持，，操作，并能在常数时间内检索到最小元素的栈。将元素推入栈中。删除栈顶的元素。示例返回返回返回解答每次入栈都放入两个元素，分别是当前元素，和当前的最小元素因此放入之前需要和当前值进行比较。题目地址：https://leetcode-cn.com/probl...题目描述：设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 p...

Scliang 2019-08-16 15:21 评论0 收藏0