前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作(java)

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

作者头像
用户5513909
发布2023-04-25 11:29:40
2840
发布2023-04-25 11:29:40
举报

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

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

在这里插入图片描述
在这里插入图片描述
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();
        }
    }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-09-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档