剑指offer：包含min函数的栈

ゞ浴缸里的玫瑰 2021-06-24 16:09 296阅读 0赞

**试题：**  
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。  
**代码：**  
为了实现栈的功能，我们可以简单的利用java Stack来存储数据，但题目要求实现一个O(1)的求栈内最小值的函数，显然直接利用stack求解无法达到要求，这就需要我们在入栈时已经将最小值求得，在出栈时直接返回。栈存在一个特点是所有数据都是按照入栈顺序排列的，那么我们可以记录一个从栈底到栈中某位置所有数值的最小值序列，提前将最小值都记录下来。如下：  
栈 3，4，2，5，1  
辅助栈 3，3，2，2，1

import java.util.Stack;
    
    public class Solution {
    
        private Stack<Integer> stack1 = new Stack<Integer>();
        private Stack<Integer> stack2 = new Stack<Integer>();
        public void push(int node) {
            stack1.push(node);
            if( stack2.empty() ){
                stack2.push(node);
            }else if( node <= stack2.peek() ){   //注意等号，对出栈有影响
                stack2.push(node);
            }
        }
        
        public void pop() {
            if( stack1.peek() == stack2.peek() ){    //如果stack1的出栈值已经到达stack2标定的当前最小值位置，stack2同时出栈。
                stack2.pop();
            }
            stack1.pop();
        }
        
        public int top() {
            return stack1.peek();
        }
        
        public int min() {
            return stack2.peek();
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，296人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer——包含min函数的栈

题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。分析：定义一个辅助栈，保存对应元素存在时当前栈中的最小元素，即可在O(1)的时间内找到最小的

叁歲伎倆/ 2022年05月31日 12:50/ 0 赞/ 129 阅读

相关剑指Offer-包含min函数的栈

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。基本思路：利用两个栈，一个数据栈，一个辅助栈（保存当前栈中数据的最小值）数据栈和辅

古城微笑少年丶/ 2022年05月23日 01:17/ 0 赞/ 123 阅读

相关剑指Offer | 包含min函数的栈

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

你的名字/ 2022年05月23日 00:35/ 0 赞/ 131 阅读

相关【剑指offer】包含min函数的栈【python】

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。算法思想，采用一个辅助栈的形式。 1. 如果pus

以你之姓@/ 2022年04月17日 00:19/ 0 赞/ 123 阅读

相关剑指offer:包含min函数的栈

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 AC C++ Solution: 使用两个栈,一个栈

缺乏、安全感/ 2022年04月10日 07:58/ 0 赞/ 158 阅读

相关【剑指offer】包含min函数的栈

包含min函数的栈题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 AC代码思路：用一个

痛定思痛。/ 2022年04月02日 15:52/ 0 赞/ 133 阅读

相关剑指Offer-包含min函数的栈

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数 (时间复杂度应为O(1))。看到题目特别是模拟编辑器上的代码，给了四个空函数，一

「爱情、让人受尽委屈。」/ 2022年02月27日 11:56/ 0 赞/ 159 阅读

相关剑指Offer——包含min函数的栈

1、题目描述　　定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 2、代码实现 package com.b

梦里梦外;/ 2021年12月04日 05:07/ 0 赞/ 203 阅读

相关剑指offer 包含min函数的栈

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为

系统管理员/ 2021年11月02日 05:04/ 0 赞/ 263 阅读

相关剑指offer：包含min函数的栈

试题：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。代码：为了实现栈的功能，我们可以简单的利用java

ゞ浴缸里的玫瑰/ 2021年06月24日 16:09/ 0 赞/ 297 阅读