实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作(java)

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

思路：建立两个栈，一个data栈压入数据（和正常的压栈一样），另一个min栈压入最小值。如果压入的数据比当前最小值小则压入min栈，大于当前最小值则重复压入当前min栈栈顶元素。 min栈和data保持同步的入栈出栈操作，这样始终保持min栈栈顶元素为最小值。

代码语言：javascript复制

public static class MyStack1 {
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack1() {
            this.stackData = new Stack<>();
            this.stackMin = new Stack<>();
        }

        public void push(int newNum) {
            // 处理min栈
            if (this.stackMin.isEmpty()) {
                this.stackMin.push(newNum);
            } else if (newNum <= this.getmin()) {
                this.stackMin.push(newNum);
            }

            // 处理data栈
            this.stackData.push(newNum);
        }

        public int pop() {
            if (this.stackData.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }

            // 弹出data栈的栈顶元素，如果此数和min栈的栈顶相等，min栈的栈顶也弹出
            int value = this.stackData.pop();
            if (value == this.getmin()) {
                this.stackMin.pop();
            }
            return value;
        }

        public int getmin() {
            if (this.stackMin.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            // 返回min栈的栈顶元素，但不弹出
            return this.stackMin.peek();
        }
    }

java min 基础 数据 同步

0 人点赞