前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指Offer面试题:19.包含Min函数的栈

剑指Offer面试题:19.包含Min函数的栈

作者头像
Edison Zhou
发布2018-08-20 16:12:47
2270
发布2018-08-20 16:12:47
举报
文章被收录于专栏:EdisonTalk

一、题目:包含Min函数的栈

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

  这里我们要实现的就是min、push以及pop三个方法:

代码语言:javascript
复制
    public class MinInStack<T> where T : struct
    {
        private Stack<T> dataStack;
        private Stack<T> minStack;

        public MinInStack()
        {
            this.dataStack = new Stack<T>();
            this.minStack = new Stack<T>();
        }

        public bool IsEmpty()
        {
            return this.dataStack.Count == 0;
        }

        public T Top()
        {
            return this.dataStack.Peek();
        }

        public void Push(T item)
        {
        }

        public T Pop()
        {
        }

        public T Min()
        {
        }
    }

二、解题思路

2.1 核心步骤

  把每次的最小元素(之前的最小元素和新压入栈的元素两者的较小值)都保存起来放到另外一个辅助栈里。下图展示了栈内压入3、4、2、1之后接连两次弹出栈顶数字再压入0时,数据栈、辅助栈和最小值的状态。

  从表中我们可以看出,如果每次都把最小元素压入辅助栈,那么就能保证辅助栈的栈顶一直都是最小元素

2.2 代码实现

  (1)Push方法

代码语言:javascript
复制
    public void Push(T item)
    {
        // 把新元素添加到数据栈
        dataStack.Push(item);
        // 当新元素比之前的最小元素小时,把新元素插入辅助栈里;
        // 否则把之前的最小元素重复插入辅助栈里
        if (minStack.Count == 0 || item.CompareTo(minStack.Peek()) < 0)
        {
            minStack.Push(item);
        }
        else
        {
            minStack.Push(minStack.Peek());
        }
    }

  (2)Pop方法

代码语言:javascript
复制
    public T Pop()
    {
        T item = dataStack.Pop();
        if(minStack.Count > 0)
        {
            minStack.Pop();
        }

        return item;
    }

  (3)Min方法

代码语言:javascript
复制
    public T Min()
    {
        return minStack.Peek();
    }

三、单元测试

3.1 测试用例

代码语言:javascript
复制
    [TestMethod]
    public void MinTest1()
    {
        MinInStack<int> stack = new MinInStack<int>();
        stack.Push(3);
        Assert.AreEqual(stack.Min(),3);
    }

    [TestMethod]
    public void MinTest2()
    {
        MinInStack<int> stack = new MinInStack<int>();
        stack.Push(3);
        stack.Push(4);
        Assert.AreEqual(stack.Min(), 3);
    }

    [TestMethod]
    public void MinTest3()
    {
        MinInStack<int> stack = new MinInStack<int>();
        stack.Push(3);
        stack.Push(4);
        stack.Push(2);
        Assert.AreEqual(stack.Min(), 2);
    }

    [TestMethod]
    public void MinTest4()
    {
        MinInStack<int> stack = new MinInStack<int>();
        stack.Push(3);
        stack.Push(4);
        stack.Push(2);
        stack.Push(3);
        Assert.AreEqual(stack.Min(), 2);
    }

    [TestMethod]
    public void MinTest5()
    {
        MinInStack<int> stack = new MinInStack<int>();
        stack.Push(3);
        stack.Push(4);
        stack.Push(2);
        stack.Push(3);
        stack.Pop();
        Assert.AreEqual(stack.Min(), 2);
    }

    [TestMethod]
    public void MinTest6()
    {
        MinInStack<int> stack = new MinInStack<int>();
        stack.Push(3);
        stack.Push(4);
        stack.Push(2);
        stack.Push(3);
        stack.Pop();
        stack.Pop();
        Assert.AreEqual(stack.Min(), 3);
    }

    [TestMethod]
    public void MinTest7()
    {
        MinInStack<int> stack = new MinInStack<int>();
        stack.Push(3);
        stack.Push(4);
        stack.Push(2);
        stack.Push(3);
        stack.Pop();
        stack.Pop();
        stack.Pop();
        Assert.AreEqual(stack.Min(), 3);
    }

    [TestMethod]
    public void MinTest8()
    {
        MinInStack<int> stack = new MinInStack<int>();
        stack.Push(3);
        stack.Push(4);
        stack.Push(2);
        stack.Push(3);
        stack.Pop();
        stack.Pop();
        stack.Pop();
        stack.Push(0);
        Assert.AreEqual(stack.Min(), 0);
    }

3.2 测试结果

  (1)测试通过情况

  (2)代码覆盖率

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-09-02 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目:包含Min函数的栈
  • 二、解题思路
    • 2.1 核心步骤
      • 2.2 代码实现
      • 三、单元测试
        • 3.1 测试用例
          • 3.2 测试结果
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档