LeetCode135|包含min函数的栈

码农王同学

发布于 2020-11-16 16:24:13

35400

代码可运行

文章被收录于专栏：后端Coder后端Coder

运行总次数：0

代码可运行

1，问题简述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

2，示例

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.
 

提示：

各函数的调用总次数不超过 20000 次

3，题解思路

使用现有的java提供的Stack来解决

4，题解程序


import java.util.Iterator;
import java.util.Stack;

public class MinStack {
    static Stack<Integer> stack = new Stack<>();

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println("stack = " + stack);
        int min = minStack.min();
        System.out.println("min = " + min);
        int pop = minStack.pop();
        System.out.println("pop = " + pop);
        int top = minStack.top();
        System.out.println("top = " + top);
        int min1 = minStack.min();
        System.out.println("min1 = " + min1);
    }

    public MinStack() {

    }

    public void push(int x) {
        stack.push(x);
    }

    public int pop() {
        Integer pop = stack.pop();
        return pop;
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        Integer min = stack.peek();
        Iterator<Integer> iterator = stack.iterator();
        while (iterator.hasNext()) {
            Integer val = iterator.next();
            if (min > val) {
                min = val;
            }
        }
        return min;
    }
}

5，题解程序图片版

6，总结一下

抱着不重复造轮子的想法，这里自己使用了java已有的栈进行了操作，其实这类题本身是一道设计类型的题，对于java开发者来说，设计类的题，大家用的都差不多，比如如何定义一个数据结构来进行业务逻辑的开发，想必你也是用的很熟练是吧，这里其实在考察你是否掌握了Stack这个数据结构的特点，栈的特点，先进后出

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-11-08，如有侵权请联系 cloudcommunity@tencent.com 删除

java