前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法题:实现最大(小)栈

算法题:实现最大(小)栈

作者头像
你好戴先生
发布2021-11-25 14:52:44
5580
发布2021-11-25 14:52:44
举报
文章被收录于专栏:戴言泛滥

##题目

实现一个最大(小)栈,即可随时拿出当前栈中最大(小)的元素 ##解题思路

这是一道非常经典的面试题,目题目也不难,但还是很能考察开发人员的基本功的,所以面试官很容易脱口就问到这个题

这道题目的要求其实就是实现一个特殊的栈

这个栈能够随时拿到栈中所有元素的最大(小)值

这就是题目所有的要求了

所以在已有栈的基础上稍加改进就能实现

比较简单的办法就是使用两个栈来实现这个特殊的栈

其中一个栈stack正常进出元素

另外一个栈stackMax(stackMin)在进元素的时候,与栈顶的元素做一个比较

如果大于(小于)栈顶元素,则正常入栈

如果小于(大于)栈顶元素,则将当前栈顶的元素再次入栈

注意:当前元素栈顶并不出栈

出栈的时候就跟随stack正常出栈

这样就能保证stackMax(stackMin)跟stack的高度永远一致

并且栈顶的元素永远是最大(小)值

##算法图解

以最大栈为例进行图解演示

定义两个栈,和一堆需要入栈的元素

当栈为空的时候,正常入栈

当栈不为空的时候,stack栈正常入栈

stackMax栈中,则需要将入栈元素“3”与栈顶元素“1”进行比较

“3”>“1”,所以将“3”正常入栈

stack栈仍然正常入栈

stackMax栈中,则需要将入栈元素“1”与栈顶元素“3”进行比较

“3”>“1”,所以将栈顶元素“3”,再次入栈

依次类推,知道所有元素入栈

在这个过程中,stackMax栈的栈顶元素,始终是最大元素

##代码实现

代码语言:javascript
复制
public class MaxHeap {
    private final Stack<Integer> stack;
    private final Stack<Integer> stackMax;

    public MaxHeap() {
        this.stack = new Stack<>();
        this.stackMax = new Stack<>();
    }

    public Integer peekMax() {
        return stackMax.peek();
    }

    public Integer push(Integer item) {
        if (stack.isEmpty()) {
            stackMax.push(item);
        } else {
            if (item > stackMax.peek()) {
                stackMax.push(item);
            } else {
                stackMax.push(stackMax.peek());
            }
        }
        stack.push(item);
        return item;
    }

    public Integer peek() {
        return stack.peek();
    }

    public Integer pop() {
        stackMax.pop();
        return stack.pop();
    }
}

文/戴先生@2021年11月18日

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-11-18,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 你好戴先生 微信公众号,前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • ##题目
  • ##算法图解
  • ##代码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档