精华内容
下载资源
问答
  • 操作步骤5 执行出栈操作,如下图所示:元素 1 出栈,判断当前元素就是栈的最小值,因此将栈顶元素 3 设置为最小值,并移除元素 3,如下图所示: 操作步骤6 继续出栈,如下图所示:因为元素 5 不是当前最小值,因此...

    作者 | 王磊

    来源 | Java中文社群(ID:javacn666)

    转载请联系授权(微信ID:GG_Stone)

    前面我们学习了很多关于栈的知识,比如《动图演示:手撸堆栈的两种实现方法!》《JDK 竟然是这样实现栈的?》,那么接下来我们再来刷一些关于栈的经典面试题以巩固学过的知识。

    我们今天的面试题是这样的...

    题目

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

    示例:

    MinStack minStack = new MinStack();

    minStack.push(-2);

    minStack.push(0);

    minStack.push(-3);

    minStack.min();   --> 返回 -3.

    minStack.pop();

    minStack.top();      --> 返回 0.

    minStack.min();   --> 返回 -2.

    LeetCode 地址:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

    思考

    首先来说这道题目本身很好理解,它的实现难点在于以下两个方面:

    • 当我们进行 pop(移除栈顶元素)操作时如果删除的是当前最小值,那么我们如何寻找下一个最小值?

    • 要保证调用 min、push 及 pop 的时间复杂度都是 O(1)。

    也就是说,在我们执行了 pop 时如果移除的栈中最小的值,那么如何寻找栈中的下一个最小元素?并且要保证操作的时间复杂度为 O(1)。这个时间复杂度制约了我们在移除了最小值之后不能通过遍历查找下一个最小值,所以这就成为了这道题的难点。

    比如当我们移除以下栈顶元素值:

    因为最小值就是 1,因此在移除之后最小值也被移除了,如下图所示:

    那么接下来,让我们一起思考 3 分钟,想一想应该如何处理这个问题~

    解题思路

    其实我们可以在每次入栈时,判断当前元素是否小于最小值,如果小于则将原最小值和最新的最小值相继入栈,这样在调用 pop 时即使移除的是最小值,我们也能通过获取下一个元素得到一个新的最小值,执行流程如下所示。

    操作步骤1

    入栈第一个元素,因为是第一个元素,因此最小值就是此元素的值。

    操作步骤2

    入栈第二个元素,如下图所示:

    因为入栈的元素 3 比 8 小,所以先将栈中的原最小值 8 存入栈中,再将 3 入栈。

    操作步骤3

    入栈第三个元素,如下图所示:因为入栈元素 5 大于 3,因此栈中的最小值不变,直接将元素 5 入栈。

    操作步骤4

    继续入栈,如下图所示:入栈元素 1 小于于 3,因此先将原最小值 3 入栈,再将 1 入栈,栈中的最小值更改为 1。

    操作步骤5

    执行出栈操作,如下图所示:元素 1 出栈,判断当前元素就是栈的最小值,因此将栈顶元素 3 设置为最小值,并移除元素 3,如下图所示:


    操作步骤6

    继续出栈,如下图所示:因为元素 5 不是当前最小值,因此直接出栈。

    操作步骤7

    继续出栈,如下图所示:因为出栈元素 3 为最小值,因此继续将最小值设置为栈顶元素 8,并将栈顶元素出栈,如下图所示:这样就剩下最后一个元素了,最后一个元素出栈之后就成空栈了,整个流程就执行完了。

    实现代码1

    接下来我们将上面的思路用代码实现一下,我们用数组实现的栈来实现相关的功能,代码如下:

    class MinStack {
        private int[] data; // 栈数据
        private int maxSize; // 最大长度
        private int top; // 栈顶指针(下标)
        private int min; // 最小值
    
        // 构造函数
        public MinStack() {
            // 设置默认值
            maxSize = 10000;
            data = new int[maxSize];
            top = -1;
            min = Integer.MAX_VALUE;
        }
    
        // 入栈(添加元素)
        public void push(int x) {
            if (min >= x) {
                // 遇到了更小的值,记录原最小值(入栈)
                data[++top] = min;
                min = x;
            }
            // 当前值入栈
            data[++top] = x;
        }
    
        // 出栈(移除栈顶元素)
        public void pop() {
            if (min == data[top]) {
                min = data[--top]; // 拿到原最小值,并(将原最小值)出栈
            }
            --top; // 出栈
        }
    
        // 查找栈顶元素
        public int top() {
            return data[top];
        }
     
        // 查询最小值
        public int min() {
            return min;
        }
    }
    

    上述代码在 LeetCode 的执行结果如下:


    可以看出性能还是很高的,超越了 99.92% 的用户,内存消耗也不大。它的核心代码在 push 方法内,先将原最小值和最新最小值相继入栈,在 pop 出栈时判断出栈元素是否为最小值,如果是最小值则将当前最小值指向栈顶元素并将栈顶元素出栈,这样就得到了下一个新的最小值了。

    实现代码2

    如果我们不想使用数组的自定义栈来实现,还可以使用 Java 中自带的栈 Stack 来实现此功能,代码如下:

    class MinStack {
        private Stack<Integer> stack = new Stack<>();
        private int min = Integer.MAX_VALUE;
    
        public MinStack() { }
    
        // 入栈(添加元素)
        public void push(int x) {
            if (x <= min) {
                // 遇到了更小的值,记录原最小值(入栈)
                stack.push(min);
                min = x;
            }
            stack.push(x);
        }
    
        // 出栈(移除栈顶元素)
        public void pop() {
            if (stack.pop() == min) {
                min = stack.pop(); // 取出原最小值
            }
        }
    
        // 查找栈顶元素
        public int top() {
            return stack.peek();
        }
    
        // 查询最小值
        public int min() {
            return min;
        }
    }
    

    上述代码在 LeetCode 的执行结果如下:


    从结果可以看出,使用 Java 中自带的栈的性能不如自定义数组的栈,但代码还是通过了测试。这种实现方式的优点就是代码比较简单,可以利用了 Java 自身的 API 来完成了最小值的查找。

    这种实现代码的方式(使用 Java API),在刷题或者实际面试中如果没有特殊说明是可以直接用的。

    总结

    本文我们通过两种方式:自定义数组栈和 Java API 中的 Stack 来实现了栈中最小值的功能,保证了在调用栈的 min、push 及 pop 方法时的时间复杂度都是 O(1)。两种实现方式的代码虽然略不相同,但实现思路都是一样的,都是在元素入栈时判断当前元素是否小于最小元素,如果小于最小元素则先将原最小值入栈,再将当前最小元素入栈,这样当调用 pop 方法时,即使移除的是最小值,只需要将下一个元素取出即为新的最小值了,这样就可以实现调用 min、push 及 pop 方法时的时间复杂度都是 O(1) 了。

    最后

    机智的你一定还有其他的实现答案,评论区告诉我吧~

    原创不易,各位素质四联,谢啦。

    
    往期推荐
    

    链表反转的两种实现方法,后一种击败了100%的用户!


    JDK 竟然是这样实现栈的?


    动图演示:手撸堆栈的两种实现方法!


    关注下方二维码,收获更多干货!

    展开全文
  • 题目定义栈的数据结构,请在该类型实现一个能够得到栈的最小元素的 min 函数在该栈,调用 min、push 及 pop 的时间复杂度都是 O(1)。示例:MinStack minStack = new MinStack();minStack.push(-2);minStack.push...

    我们今天的面试题是这样的...

    题目

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

    示例:

    MinStack minStack = new MinStack();

    minStack.push(-2);

    minStack.push(0);

    minStack.push(-3);

    minStack.min(); --> 返回 -3.

    minStack.pop();

    minStack.top(); --> 返回 0.

    minStack.min(); --> 返回 -2.

    LeetCode 地址:leetcode-cn.com/problems/ba…

    思考

    首先来说这道题目本身很好理解,它的实现难点在于以下两个方面:

    • 当我们进行 pop(移除栈顶元素)操作时如果删除的是当前最小值,那么我们如何寻找下一个最小值?
    • 要保证调用 min、push 及 pop 的时间复杂度都是 O(1)。

    也就是说,在我们执行了 pop 时如果移除的栈中最小的值,那么如何寻找栈中的下一个最小元素?并且要保证操作的时间复杂度为 O(1)。这个时间复杂度制约了我们在移除了最小值之后不能通过遍历查找下一个最小值,所以这就成为了这道题的难点。

    比如当我们移除以下栈顶元素值:

    8f702ffd99739465b4bcb6dbfa1c756c.png

    因为最小值就是 1,因此在移除之后最小值也被移除了,如下图所示:

    d952b011b981c0056668a2ace086fe30.png

    那么接下来,让我们一起思考 3 分钟,想一想应该如何处理这个问题~

    解题思路

    其实我们可以在每次入栈时,判断当前元素是否小于最小值,如果小于则将原最小值和最新的最小值相继入栈,这样在调用 pop 时即使移除的是最小值,我们也能通过获取下一个元素得到一个新的最小值,执行流程如下所示。

    操作步骤1

    入栈第一个元素,因为是第一个元素,因此最小值就是此元素的值。

    4ca1581196782965002bb3a132b211c9.png

    操作步骤2

    入栈第二个元素,如下图所示:

    8255e9630601e9efa87e634aad9de6e5.png

    因为入栈的元素 3 比 8 小,所以先将栈中的原最小值 8 存入栈中,再将 3 入栈。

    操作步骤3

    入栈第三个元素,如下图所示:

    f34aea8d128dd964e9673a9ea9c1d28a.png

    因为入栈元素 5 大于 3,因此栈中的最小值不变,直接将元素 5 入栈。

    操作步骤4

    继续入栈,如下图所示:

    a692d02a61f30622d21b255fda6e2041.png

    入栈元素 1 小于 3,因此先将原最小值 3 入栈,再将 1 入栈,栈中的最小值更改为 1。

    操作步骤5

    执行出栈操作,如下图所示: [图片上传中...(image-f68dcf-1602769401330-6)]

    元素 1 出栈,判断当前元素就是栈的最小值,因此将栈顶元素 3 设置为最小值,并移除元素 3,如下图所示:

    9668c6fba082c3fe640b457e4e6f4657.png

    操作步骤6

    继续出栈,如下图所示:

    110c0f03d24ac4e20f609968a1ebee4f.png

    因为元素 5 不是当前最小值,因此直接出栈。

    操作步骤7

    继续出栈,如下图所示:

    1c9437be519c808da9c61fabc24ed94e.png

    因为出栈元素 3 为最小值,因此继续将最小值设置为栈顶元素 8,并将栈顶元素出栈,如下图所示:

    19cc0ea6e1966ce0647c2f36e11175f0.png

    这样就剩下最后一个元素了,最后一个元素出栈之后就成空栈了,整个流程就执行完了。

    实现代码1

    接下来我们将上面的思路用代码实现一下,我们用数组实现的栈来实现相关的功能,代码如下:

    class MinStack {    private int[] data; // 栈数据    private int maxSize; // 最大长度    private int top; // 栈顶指针(下标)    private int min; // 最小值    // 构造函数    public MinStack() {        // 设置默认值        maxSize = 10000;        data = new int[maxSize];        top = -1;        min = Integer.MAX_VALUE;    }    // 入栈(添加元素)    public void push(int x) {        if (min >= x) {            // 遇到了更小的值,记录原最小值(入栈)            data[++top] = min;            min = x;        }        // 当前值入栈        data[++top] = x;    }    // 出栈(移除栈顶元素)    public void pop() {        if (min == data[top]) {            min = data[--top]; // 拿到原最小值,并(将原最小值)出栈        }        --top; // 出栈    }    // 查找栈顶元素    public int top() {        return data[top];    }    // 查询最小值    public int min() {        return min;    }}

    上述代码在 LeetCode 的执行结果如下:

    0fd6255a54fb214116382090c7847f4f.png

    可以看出性能还是很高的,超越了 99.92% 的用户,内存消耗也不大。它的核心代码在 push 方法内,先将原最小值和最新最小值相继入栈,在 pop 出栈时判断出栈元素是否为最小值,如果是最小值则将当前最小值指向栈顶元素并将栈顶元素出栈,这样就得到了下一个新的最小值了。

    实现代码2

    如果我们不想使用数组的自定义栈来实现,还可以使用 Java 中自带的栈 Stack 来实现此功能,代码如下:

    class MinStack {    private Stack stack = new Stack<>();    private int min = Integer.MAX_VALUE;    public MinStack() { }    // 入栈(添加元素)    public void push(int x) {        if (x <= min) {            // 遇到了更小的值,记录原最小值(入栈)            stack.push(min);            min = x;        }        stack.push(x);    }    // 出栈(移除栈顶元素)    public void pop() {        if (stack.pop() == min) {            min = stack.pop(); // 取出原最小值        }    }    // 查找栈顶元素    public int top() {        return stack.peek();    }    // 查询最小值    public int min() {        return min;    }}

    上述代码在 LeetCode 的执行结果如下:

    203f4078ebc41d22bd3aea1377cab7c4.png

    从结果可以看出,使用 Java 中自带的栈的性能不如自定义数组的栈,但代码还是通过了测试。这种实现方式的优点就是代码比较简单,可以利用了 Java 自身的 API 来完成了最小值的查找。

    这种实现代码的方式(使用 Java API),在刷题或者实际面试中如果没有特殊说明是可以直接用的。

    总结

    本文我们通过两种方式:自定义数组栈和 Java API 中的 Stack 来实现了栈中最小值的功能,保证了在调用栈的 min、push 及 pop 方法时的时间复杂度都是 O(1)。两种实现方式的代码虽然略不相同,但实现思路都是一样的,都是在元素入栈时判断当前元素是否小于最小元素,如果小于最小元素则先将原最小值入栈,再将当前最小元素入栈,这样当调用 pop 方法时,即使移除的是最小值,只需要将下一个元素取出即为新的最小值了,这样就可以实现调用 min、push 及 pop 方法时的时间复杂度都是 O(1) 了。

    最后

    机智的你一定还有其他的实现答案,评论区告诉我吧~
    原创不易,各位素质四联,谢啦。
    大家看完有什么不懂的可以在下方留言讨论.
    谢谢你的观看。
    觉得文章对你有帮助的话记得关注我点个赞支持一下!

    作者:Java中文社群
    链接:https://juejin.im/post/6883828072227799047

    展开全文
  • 定义栈的数据结构,添加min()、max()函数(动态获取当前状态栈的最小元素、最大元素),要求push()、pop()、min()、max()的时间复杂度都是O(1)。

    题目要求:定义栈的数据结构,添加min()、max()函数(动态获取当前状态栈中的最小元素、最大元素),要求push()、pop()、min()、max()的时间复杂度都是O(1)。

    思路解析:根据栈的后进先出特性,增加辅助栈,来存储当前状态下数据栈中的最小、最大元素。


    代码:(python实现)

    #coding=utf-8
    
    class Stack(object):
        
        def __init__(self):
            self.data = []
            self.minValue = []
            self.maxValue = []
        
        def push(self, data):
            self.data.append(data)
            if len(self.minValue) == 0:
                self.minValue.append(data)
            else:
                if data <= self.minValue[-1]:
                    self.minValue.append(data)
            if len(self.maxValue) == 0:
                self.maxValue.append(data)
            else:
                if data >= self.maxValue[-1]:
                    self.maxValue.append(data)
        
        def pop(self):
            if len(self.data) == 0:
                return None
            else:
                temp = self.data.pop()
                if temp == self.minValue[-1]:
                    self.minValue.pop()
                if temp == self.maxValue[-1]:
                    self.maxValue.pop()
                return temp
        
        def min(self):
            if len(self.data) == 0:
                return None
            else:
                return self.minValue[-1]
        
        def max(self):
            if len(self.data) == 0:
                return None
            else:
                return self.maxValue[-1]
        
        def show(self):
            print 'stack data:'
            for data in self.data:
                print data,
            print
            print 'min : ', self.min()
            print 'max : ', self.max()
        
        
    if __name__ == '__main__':
        s = Stack()
        s.push(2)
        s.push(1)
        s.show()
        s.push(4)
        s.push(3)
        s.push(2)
        s.show()
        s.pop()
        s.show()
        s.pop()
        s.show()


    展开全文
  • 题目要求:定义栈的数据结构,添加min()、max()函数(动态获取当前状态栈的最小元素、最大元素),要求push()、pop()、min()、max()的时间复杂度都是O(1)。 思路解析:根据栈的后进先出特性,增加辅助栈,来存储...

    题目要求:定义栈的数据结构,添加min()、max()函数(动态获取当前状态栈中的最小元素、最大元素),要求push()、pop()、min()、max()的时间复杂度都是O(1)。

    思路解析:根据栈的后进先出特性,增加辅助栈,来存储当前状态下数据栈中的最小、最大元素。

    原文:http://blog.csdn.net/happy309best/article/details/47725935

    class Solution:
        def __init__(self):
            self.data=[]
            self.min_data=[]
        def push(self, node):
            self.data.append(node)
            if len(self.min_data)==0 or node<=self.min_data[len(self.min_data)-1]:
                self.min_data.append(node)
        def pop(self):
            if len(self.data)>0:
                val=self.data.pop()
                if val==self.min_data[len(self.min_data)-1]:
                    self.min_data.pop()
                return val
        def top(self):
            if len(self.data)>0:
                return self.data[len(self.data)-1]
            return None
        def min(self):
            if len(self.min_data)>0:
                return self.min_data[len(self.min_data)-1]
            return None

     

    转载于:https://www.cnblogs.com/gczr/p/7124502.html

    展开全文
  • *操作 创建 出栈 入栈 取栈顶元素 *创建数据域的结构体 *创建数据域的名称指针 *使用随机函数对数据域的编号进行赋值 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<....
  • #include<stdio.h> #define MAXSIZE 100 typedef struct{ int *base;... //为顺序栈动态分配一个最大容量为MAXSIZE的数组 if(!S.base) return false; S.top=S.base; //设置为空栈 S.stacksiz
  • cout 木有最大元素鸟~~~" ; return -1; } return * ( value_top ); } void main() { stack_top = stack_base; value_top = max_value; int i; for( i = 0 ; i ; i ++ ) { push( rand() % 100 ); } } ...
  • 栈的一些性质: 1.栈为空不可以出栈 2.栈顶元素先出 3.新元素插入栈顶 ...template //模板,表示可以"动态"定义Stack某些数据元素的类型,这样的话可以增加代码的重用性 class Stack{ private: Type
  • Code /*顺序表实现栈的一系列操作*/ #include<stdio.h> #include<stdlib.h>...#define Stack_Size 50 //设栈中元素个数为50 #define OK 1 #define ERROR 0 typedef struct ...
  • 代码段: #include<...#define MaxSize 50//定义栈最大长深度 #define ElemType int//把int命名为ElemType typedef struct { ElemType data[MaxSize];//存放栈元素 int top; //栈顶指针 }SqSt
  • njupt 字典序最大出栈序列

    千次阅读 2013-07-24 11:53:50
    /* 题意:给出入栈序列{A},保证{A}各个元素值各不相等,输出字典序最大出栈序列. 如入栈序列{A} = 1, 2, 9, 4, 6, 5 则字典序最大出栈序列为9, 6, 5, 4, 2 1 思路:栈的性质就是先进后出,所以对于依次...
  • 这么说吧,网上的解释看着蛋疼,...现在有一个容量为m的栈S,有n个元素在栈S顶端一侧等待进栈,另一侧是出栈序列。现在要使用push和pop这两种操作,由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的...
  • 模拟出栈

    2019-03-12 19:03:00
    给定一个最大容量为M的堆栈,将N个数字按 1, 2, 3, ...,N的顺序入栈,允许按任何顺序出栈,则哪些数字序列是不可能得到的?例如给定M=5、N=7,则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 },但不可能得到{ 3, 2, 1, 7, ...
  • if(S->top) //压入栈元素不能超过栈的最大存储 { printf(“输入入栈字符元素:\n”); for(i=0;i { scanf(" %c",&ch); S->top++; //移动栈顶指针 S->elem[S->top]=ch; } } } void Output(SeqStack *S) { int i; ...
  • 出栈次序

    2021-05-08 17:11:06
    本题为填空题,只需要算出结果后,在代码使用输出语句将所填结果输出即可。 X 星球特别讲究秩序,所有道路都是单行线。一个甲壳虫车队,共 161616 辆车,按照编号先后发车,夹在其它车流,缓缓前行。 路边有个...
  • 本文纯属个人见解,是对前面学习的总结,如有描述不正确的地方还请...入栈序列为 1 2 3 4 5,则 1 2 3 4 5可能为它的出栈序列,而 5 4 1 2 3弗成能为它的出栈序列。 对于n比较小的情况,我们往往可以通过手动模拟...
  • 咱们明天的面试题是这样的…题目定义栈的数据结构,请在该类型实现一个可能失去栈的最小元素的 min 函数在该栈,调用 min、push 及 pop 的工夫复杂度都是 O(1)。示例:MinStack minStack = new...
  • 18715 出栈序列

    2021-04-22 20:20:57
    18715 出栈序列 时间限制:1000MS 代码长度限制:10KB ...现在有一个1-n的排列,入栈序列已知,请给出字典序最大出栈序列。 输入格式 第一行一个整数n。(1<=n<=100) 第二行n个整数,数据确保为1-n的排列
  • //头文件 #ifndef STACKLIST_H #define STACKLIST_H #include #include #include using namespace std; template class StackList{ private: ...//栈的最大空间 int top;//标记栈顶
  • 数组模拟入栈出栈

    2020-03-21 19:48:32
    首先对栈做一个简单的介绍,栈是一个先入后... 删除:在栈删除操作称为出栈,最先删除的元素在栈顶,最后删除的元素在栈底。 入栈和出栈示意图: 实现栈的思路: 使用数组来模拟(单链表也是可以的); 定义...
  • 出栈序列统计

    千次阅读 2013-12-27 09:02:51
    问题描述:栈是常用的一种数据结构,有n令元素在栈顶端一侧等待进栈,栈顶端另一侧是出栈序列。你已经知道栈的操作有两·种:push和pop,前者是将一个元素进栈,后者是将栈顶元素弹出。现在要使用这两种操作,由一个...
  • 出栈序列问题

    千次阅读 2011-11-19 20:03:59
    关于出栈序列问题,我纠结很久,但总是感觉心里还有一点结。 题目:对于一个入栈顺序已知,求出所有的出栈序列。 在此可以将题 目简化一下(因为我们更多的关系出栈的序列,而不关心栈里装的是什么)。 题目:对...
  • OpenJudge进栈出栈2

    2020-03-24 22:23:43
    OpenJudge进栈出栈2 描述 1~N范围内的所有自然数按照从小到大的顺序(1,2,...,N)依次等待进栈。 比如现在N=3: 我们知道有些出栈顺序是合法的,例如{3,2,1}/{1,2,3}等 而有些出栈顺序是不可能出现(非法)的,...
  • 入栈和出栈

    2020-05-08 10:11:52
    下面们来说一下堆栈压入和弹出操作首先我们来看一下堆栈的定义,这是我们现实生活应用的是堆栈什么场景呢?我们这些碟子落在一起,大家想象一下,如果我们想取,盘子是不是从上面开始取呢?如图 如果你想取下边的...
  • 出栈序列的合法性

    2021-03-08 13:07:37
    出栈序列的合法性 ...输入第一行给出 3 个不超过 1000 的正整数:M(堆栈最大容量)、N(入栈元素个数)、K(待检查的出栈序列个数)。最后 K 行,每行给出 N 个数字的出栈序列。所有同行数字以空格间隔。
  • 已知从1至n的数字序列,按顺序入栈,每个数字入栈后即可出栈,也可在栈停留,等待后面的数字入栈后,该数字在出栈,求该数字序列的出栈序列是否合法? 图示: 思路 想要了解一个数字序列的出栈顺序是否合法,最为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,392
精华内容 14,956
关键字:

找出栈中最大元素