【牛客刷题专栏】0x28:JZ30 包含min函数的栈(C语言编程题)

前言

• 个人推荐在牛客网刷题(点击可以跳转)，它登陆后会保存刷题记录进度，重新登录时写过的题目代码不会丢失。
• 个人刷题练习系列专栏：个人CSDN牛客刷题专栏。 题目来自：牛客/题库 / 在线编程 / 剑指offer：
  

---

问题描述：

• 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

• 此栈包含的方法有：
  push(value):将value压入栈中
  pop():弹出栈顶元素
  top():获取栈顶元素
  min():获取栈中最小元素

• 数据范围：操作数量满足 0≤n≤300 ，输入的元素满足 ∣val∣≤10000

• 进阶：栈的各个操作的时间复杂度是 O(1) ，空间复杂度是 O(n)

示例：
输入:    ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
输出:    -1,2,1,-1
解析:
"PSH-1"表示将-1压入栈中，栈中元素为-1
"PSH2"表示将2压入栈中，栈中元素为2，-1
“MIN”表示获取此时栈中最小元素==>返回-1
"TOP"表示获取栈顶元素==>返回2
"POP"表示弹出栈顶元素，弹出2，栈中元素为-1
"PSH1"表示将1压入栈中，栈中元素为1，-1
"TOP"表示获取栈顶元素==>返回1
“MIN”表示获取此时栈中最小元素==>返回-1

---

举例：

//示例1：
//输入：["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
//返回值：
-1,2,1,-1

---

解法思路：

• 核心由于栈先进后出的特殊性

---

代码结果：

static int stack[301];
static int i = 0;
static int min_num = 99999;  
//假设的最小值，其实比栈中所有数都大，为的就是给机会找出栈中真正的最小值void push(int value ) {stack[i++] = value;
}void pop() {i--;  //只弹出，不返回值，只需指针减1
}int top() {int top_num = stack[--i];i++;return top_num;
}int min() {int min;  //这才是真正的最小值for(int k = 0 ; k < i; k++)  //来嘛，一个个比较，看谁小if(stack[k] < min_num)min_num = stack[k];  //好，你更小，最小值让给你min = min_num;   //正式接位最小值min_num = 999999;   //min函数不止用一次，下次还得与假设的最小值开始比，所以要还原return min;}

---

---

结束语

• 以上就是该C语言编程题的内容。可以在牛客尝试刷几道题目来练习实践。牛客网刷题(点击可以跳转)，可以尝试注册使用。
• 题目来自：牛客/题库 / 在线编程 / 剑指offer：