面试官：来，用Golang设计并实现一个有getMin功能的栈~

谁践踏了优雅 2022-09-12 08:56 182阅读 0赞

题目：在实现栈的基本功能基础上，再实现返回栈中最小元素的操作。

要求：

1.  pop、push、getMin操作的时间复杂度都是O(1)。
2.  设计的栈类型可以使用现成的栈结构。

解答：维护两个栈，一个栈保存当前栈中的元素，其功能和正常的栈一样，记为stackData，另一个保存每一步操作的最小值，记为stackMin，调用getMin方法时，返回stackMin栈的栈顶元素即可。

具体实现方案有AB两种。

**A压入数据规则：**

1.  假设当前数据为newNum，先将其压入stackData，然后判断stackMin是否为空。
2.  stackMin为空，则newNum也压入stackMin。
3.  stackMin不为空，则比较newNum和stackMin栈顶元素哪个更小。
4.  newNum更小或两者相等，则newNum也压入stackMin。
5.  stackMin栈顶元素更小，则stackMin不压入任何内容。

A举个栗子：依次压入3、4、5、1、2、1的过程，stackData和stackMin变化过程如下图：

![4355b7c1e46d466db429f2a7801df372.png][]

**A弹出数据规则：**

1.  先弹出stackData中栈顶元素记为value，与stackMin栈顶元素比较。
2.  由【A压入数据规则】可知，stackMin中存在的元素是从栈顶到栈地逐渐变大的，stackMin栈顶元素即是stackMin中最小的元素，也是stackData中最小的元素，因此不会出现value比stackMin栈顶元素更小的情况，只可能大于或等于stackMin栈顶元素。
3.  当value等于stackMin栈顶元素时，stackMin弹出栈顶元素，大于stackMin栈顶元素时，直接返回value。

**A查询当前栈中最小值操作：**

由【A压入数据规则】和【A弹出数据规则】可知，stackMin始终记录着stackData中的最小值，所以stackMin栈顶元素始终是当前stackData中的最小值。

来看下方案A的Golang代码实现：

/* *                    .::::. *                  .::::::::. *                 ::::::::::: *             ..:::::::::::' *           '::::::::::::' *             .:::::::::: *        '::::::::::::::.. *             ..::::::::::::.    Utils:stack 栈和队列 *           ``::::::::::::::::    Author:崔金朋 *            ::::``:::::::::'        .:::. *           ::::'   ':::::'       .::::::::. *         .::::'      ::::     .:::::::'::::. *        .:::'       :::::  .:::::::::' ':::::. *       .::'        :::::.:::::::::'      ':::::. *      .::'         ::::::::::::::'         ``::::. *  ...:::           ::::::::::::'              ``::. * ```` ':.          ':::::::::'                  ::::.. *                 '.:::::'                ':'````.. */package mainimport ("errors")type Stack struct {
         stackData []interface{}  stackMin  []interface{}}func (s *Stack) Push(item interface{}) (bool, error) {
       if item == nil {
       return false, errors.New("数据不能为空")  }var newNum int  newNum, numErr := CheckNum(item)if numErr != nil || newNum == 0 {
       return false, numErr  }  s.stackData = append(s.stackData, newNum)if len(s.stackMin) == 0 {
           s.stackMin = append(s.stackMin, newNum)  } else {
           minNum, minErr := s.GetMin()if minNum == 0 || minErr != nil {
             s.stackMin = append(s.stackMin, newNum)    } else if newNum <= minNum {
             s.stackMin = append(s.stackMin, newNum)    }  }return true, nil}func (s *Stack) Pop() (interface{}, error) {
         length := len(s.stackData)var item interface{}if length == 0 {
       return item, errors.New("数据不存在")  } else if length == 1 {
           item = s.stackData[0]    s.stackData = nil  } else {
           item = s.stackData[length-1]    s.stackData = s.stackData[0 : length-1]  }  num, numErr := CheckNum(item)if numErr != nil || num == 0 {
       return num, numErr  }  minNum, minErr := s.GetMin()if minNum == 0 || minErr != nil {
       return minNum, minErr  }if num == minNum {
           val, valErr := s.PopMin()return val, valErr  }return num, nil}func (s *Stack) PopMin() (int, error) {
         length := len(s.stackMin)var item interface{}if length == 0 {
       return 0, errors.New("数据不存在")  } else if length == 1 {
           item = s.stackMin[0]    s.stackMin = nil  } else {
           item = s.stackMin[length-1]    s.stackMin = s.stackMin[0 : length-1]  }  num, numErr := CheckNum(item)if numErr != nil || num == 0 {
       return num, numErr  }return num, errors.New("Min")}func (s *Stack) GetMin() (int, error) {
         length := len(s.stackMin)var item interface{}if length == 0 {
       return 0, errors.New("数据不存在")  }if length == 1 {
           item = s.stackMin[0]  } else {
           item = s.stackMin[length-1]  }  num, numErr := CheckNum(item)if numErr != nil || num == 0 {
       return num, numErr  }return num, nil}func CheckNum(item interface{}) (int, error) {
       switch item := item.(type) {
       case int:return item, nildefault:return 0, errors.New("数据类型错误")  }}

**B压入数据规则：**

1.  假设当前数据为newNum，先将其压入stackData，然后判断stackMin是否为空。
2.  stackMin为空，则newNum也压入stackMin。
3.  stackMin不为空，则比较newNum和stackMin栈顶元素哪个更小。
4.  newNum更小或两者相等，则newNum也压入stackMin。
5.  stackMin栈顶元素更小，则把stackMin栈顶元素重复压入stackMin，也就是说在栈顶元素上再压入一个栈顶元素。

B举个栗子：依次压入3、4、5、1、2、1的过程，stackData和stackMin变化过程如下图：

![87b767c7a1be7ce52d4e7612e9ed2dd0.png][]

**B弹出数据规则：**

1.  先弹出stackData中栈顶元素记为value。
2.  弹出stackMin栈顶元素。
3.  返回value。

**B查询当前栈中最小值操作：**

由【B压入数据规则】和【B弹出数据规则】可知，stackMin始终记录着stackData中的最小值，所以stackMin栈顶元素始终是当前stackData中的最小值。

来看下方案B的Golang代码实现：

/* *                    .::::. *                  .::::::::. *                 ::::::::::: *             ..:::::::::::' *           '::::::::::::' *             .:::::::::: *        '::::::::::::::.. *             ..::::::::::::.    Utils:stack 栈和队列 *           ``::::::::::::::::    Author:崔金朋 *            ::::``:::::::::'        .:::. *           ::::'   ':::::'       .::::::::. *         .::::'      ::::     .:::::::'::::. *        .:::'       :::::  .:::::::::' ':::::. *       .::'        :::::.:::::::::'      ':::::. *      .::'         ::::::::::::::'         ``::::. *  ...:::           ::::::::::::'              ``::. * ```` ':.          ':::::::::'                  ::::.. *                 '.:::::'                ':'````.. */package mainimport ("errors")type Stack2 struct {
         stackData []interface{}  stackMin  []interface{}}func (s *Stack2) Push2(item interface{}) (bool, error) {
       if item == nil {
       return false, errors.New("数据不能为空")  }var newNum int  newNum, numErr := CheckNum2(item)if numErr != nil || newNum == 0 {
       return false, numErr  }  s.stackData = append(s.stackData, newNum)if len(s.stackMin) == 0 {
           s.stackMin = append(s.stackMin, newNum)  } else {
           minNum, minErr := s.GetMin2()if minNum == 0 || minErr != nil {
             s.stackMin = append(s.stackMin, newNum)    } else if newNum < minNum {
             s.stackMin = append(s.stackMin, newNum)    } else if newNum == minNum {
             s.stackMin = append(s.stackMin, newNum)    } else {
             s.stackMin = append(s.stackMin, minNum)    }  }return true, nil}func (s *Stack2) Pop2() (interface{}, error) {
         length := len(s.stackData)var item interface{}if length == 0 {
       return item, errors.New("数据不存在")  } else if length == 1 {
           item = s.stackData[0]    s.stackData = nil  } else {
           item = s.stackData[length-1]    s.stackData = s.stackData[0 : length-1]  }  num, numErr := CheckNum2(item)if numErr != nil || num == 0 {
       return num, numErr  }  s.PopMin2()return num, nil}func (s *Stack2) PopMin2() (int, error) {
         length := len(s.stackMin)var item interface{}if length == 0 {
       return 0, errors.New("数据不存在")  } else if length == 1 {
           item = s.stackMin[0]    s.stackMin = nil  } else {
           item = s.stackMin[length-1]    s.stackMin = s.stackMin[0 : length-1]  }  num, numErr := CheckNum2(item)if numErr != nil || num == 0 {
       return num, numErr  }return num, errors.New("Min")}func (s *Stack2) GetMin2() (int, error) {
         length := len(s.stackMin)var item interface{}if length == 0 {
       return 0, errors.New("数据不存在")  }if length == 1 {
           item = s.stackMin[0]  } else {
           item = s.stackMin[length-1]  }  num, numErr := CheckNum2(item)if numErr != nil || num == 0 {
       return num, numErr  }return num, nil}func CheckNum2(item interface{}) (int, error) {
       switch item := item.(type) {
       case int:return item, nildefault:return 0, errors.New("数据类型错误")  }}

上述AB都是使用stackMin栈保存着stackData每一次操作的最小值，操作的时间复杂度是都O(1)、空间复杂度都是O(n)。

上述AB的区别也很明显，A中stackMin压入时稍省空间，但是弹出操作稍费时间，B中stackMin压入时稍费空间，但是弹出操作稍省时间。

**扫码关注公众号，获取更多优质内容。**

**![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbHV5YXJhbg_size_15_color_FFFFFF_t_70_g_se_x_16][]**

[4355b7c1e46d466db429f2a7801df372.png]: /images/20220828/4037b7ce623b4771b614218a4b893d22.png
[87b767c7a1be7ce52d4e7612e9ed2dd0.png]: /images/20220828/35fa36ae01024561b14a669af760fbb6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbHV5YXJhbg_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/9f97805a732945658a9df0f1dcc87e6b.png

发表评论取消回复

表情：

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

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

相关阅读

相关算法案例(2)----------实现一个具有getMin功能的栈

零、简介记录左程云大神的程序员代码面试指南一书里面的算法实现。代码路径： [https://github.com/1956025812/algo

布满荆棘的人生/ 2023年06月27日 08:49/ 0 赞/ 4 阅读

相关【栈与队列_1】设计一个有getMin功能的栈

> 实现自己梦想的最好方式就是学习~ 目录【题目】【要求】【难度】【解答】 1. 压入数据规则 2. 弹出数据

﹏ヽ暗。殇╰゛Y/ 2022年12月22日 06:26/ 0 赞/ 144 阅读

相关面试官：来，用Golang设计并实现一个有getMin功能的栈~

题目：在实现栈的基本功能基础上，再实现返回栈中最小元素的操作。要求： 1. pop、push、getMin操作的时间复杂度都是O(1)。 2. 设计的栈类型可以使用

谁践踏了优雅/ 2022年09月12日 08:56/ 0 赞/ 183 阅读

相关设计一个递归函数来逆序一个栈，用Golang实现

题目：一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底依次为1、2、3、4、5，也就是实现栈中元素的逆序。要求：只可

我不是女神ヾ/ 2022年09月12日 08:56/ 0 赞/ 152 阅读

相关栈和队列——设计一个有getMin功能的栈（二）

【题目】　　设计一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作　　【要求】　　1、pop、push、getMin操作的时间复杂度

红太狼/ 2022年06月09日 06:20/ 0 赞/ 145 阅读

相关栈和队列——设计一个有getMin功能的栈（一）

【题目】　　设计一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作　　【要求】　　1、pop、push、getMin操作的时间复杂度

电玩女神/ 2022年06月09日 05:54/ 0 赞/ 143 阅读

相关设计一个有getMin功能的栈

【题目】实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小的元素的操作。【要求】 1、pop、push、getMin操作的时间复杂度都是O(1)

Dear 丶/ 2022年02月24日 03:40/ 0 赞/ 203 阅读

相关很有想法的一个问题---用栈实现队列和用队列实现栈

1.栈实现队列：思路是有两个栈，一个用来放数据（数据栈），一个用来辅助（辅助栈）。数据添加时，会依次压人栈，取数据时肯定会取栈顶元素，但我们想模拟队列的先进先出，所以就得

蔚落/ 2021年11月11日 20:04/ 0 赞/ 288 阅读

相关编写具有 getMin() 功能的栈

include <iostream> include <stack> using namespace std; class MySta

柔情只为你懂/ 2021年11月10日 22:12/ 0 赞/ 259 阅读

相关用两个栈来实现一个队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。 import java.util.Stack; public class

谁践踏了优雅/ 2021年09月23日 09:20/ 0 赞/ 287 阅读