[编程题]设计getMin功能的栈
- 热度指数：14902 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
实现一个特殊功能的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
输入描述:
第一行输入一个整数N，表示对栈进行的操作总数。
下面N行每行输入一个字符串S，表示操作的种类。
如果S为"push"，则后面还有一个整数X表示向栈里压入整数X。
如果S为"pop"，则表示弹出栈顶操作。
如果S为"getMin"，则表示询问当前栈中的最小元素是多少。
输出描述:
对于每个getMin操作，输出一行表示当前栈中的最小元素是多少。
示例1
输入
6 push 3 push 2 push 1 getMin pop getMin
输出
1 2
备注:
1<=N<=1000000
-1000000<=X<=1000000
数据保证没有不合法的操作
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Main specialStack = new Main();
List<Integer> resultList = new ArrayList<>();
Scanner scanner = new Scanner(System.in);
//接收键盘输入
if (scanner.hasNext()) {
int N = scanner.nextInt();
Scanner commandScanner = new Scanner(System.in);
while (N > 0 && commandScanner.hasNextLine()) {
String s = commandScanner.nextLine();
if (s.startsWith("push")) {
int newNum = Integer.parseInt(s.split(" ")[1]);
specialStack.push(newNum);
} else {
if (s.startsWith("pop")) {
specialStack.pop();
}
if (s.equals("getMin")) {
resultList.add(specialStack.getMin());
}
}
N--;
}
commandScanner.close();
}
scanner.close();
resultList.forEach(System.out::println);
}
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public Main() {
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
public void push(int newNum) {
if (stackMin.isEmpty()) {
stackMin.push(newNum);
} else if (newNum < this.getMin()) {
stackMin.push(newNum);
}
stackData.push(newNum);
}
public int pop() {
if (stackData.isEmpty()) {
throw new RuntimeException("栈空，无法弹出元素");
}
int value = stackData.pop();
if (value == this.getMin()) {
stackMin.pop();
}
return value;
}
public int getMin() {
if (stackMin.isEmpty()) {
throw new RuntimeException("栈空，不能获取最小元素");
}
return stackMin.peek();
}
}
发表于 2022-07-14 22:09:39
回复(0)
import java.util.*;
public class Main{
int arr[];//栈
int length=0;//最大长度
int p=-1;//栈帧
Main(int n){
this.length=n;
arr=new int[n];
}
public boolean isFull(){
if(length<=0)return true;
else{
if(p<length-1)return false;
else
return true;
}
}
public boolean isEmpty(){
if(length<=0)return true;
else{
if(p==-1)return true;
else return false;
}
}
public void push(int i){
if(!isFull()){
arr[++p]=i;
}
}
public int pop(){
if(!isEmpty()){
int temp=arr[p--];
//System.out.println(temp+"");
return temp;
}
return -1;
}
public void getMin(){
int min=Integer.MAX_VALUE;
for(int i=0;i<=p;i++)
min=Math.min(min,arr[i]);
System.out.println(min);
}
public static void main(String[]args){
Scanner scanner=new Scanner(System.in);
Main m=new Main(100);
int n=scanner.nextInt();
for(int i=0;i<n;i++){
String s=scanner.next();
if(s.equals("getMin")){
m.getMin();
}else if(s.equals("push")){
int i1=scanner.nextInt();
m.push(i1);
}else{
m.pop();
}
}
}
}
发表于 2022-06-08 09:22:57
回复(0)
跟着书本写的，java版本，改成c++费劲，就先用java来学习先。
方法1
import java.util.*;
class MyStack1{
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack1(){
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}
public void push(int newNum){
if(this.stackMin.isEmpty()){
this.stackMin.push(newNum);
}else if(newNum <= this.getmin()){
this.stackMin.push(newNum);
}
this.stackData.push(newNum);
}
public int pop(){
if(this.stackData.isEmpty()){
throw new RuntimeException("Your stack is empty");
}
int value = this.stackData.pop();
if(value == this.getmin()){
this.stackMin.pop();
}
return value;
}
public int getmin(){
if(this.stackMin.isEmpty()){
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
MyStack1 stack1 = new MyStack1();
int t = scan.nextInt();
for(int i=0;i<t;i++){
String op=scan.next();
if(op.equals("push")){
int x= scan.nextInt();
stack1.push(x);
}else if(op.equals("getMin")){
System.out.println(stack1.getmin());
}else if(op.equals("pop")){
stack1.pop();
}
}
}
} 方法2
import java.util.*;
class MyStack2{
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
public MyStack2(){
this.stackData = new Stack<Integer>();
this.stackMin = new Stack<Integer>();
}
public void push(int newNum){
if(this.stackMin.isEmpty()){
this.stackMin.push(newNum);
}else if(newNum < this.getmin()){
this.stackMin.push(newNum);
}else{//压入之前的最小值
int newMin = this.stackMin.peek();
this.stackMin.push(newMin);
}
this.stackData.push(newNum);
}
public int pop(){
if(this.stackData.isEmpty()){
throw new RuntimeException("Your stack is empty");
}
this.stackMin.pop();
return this.stackData.pop();
}
public int getmin(){
if(this.stackMin.isEmpty()){
throw new RuntimeException("Your stack is empty.");
}
return this.stackMin.peek();
}
}
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
MyStack2 stack2 = new MyStack2();
int t = scan.nextInt();
for(int i=0;i<t;i++){
String op=scan.next();
if(op.equals("push")){
int x= scan.nextInt();
stack2.push(x);
}else if(op.equals("getMin")){
System.out.println(stack2.getmin());
}else if(op.equals("pop")){
stack2.pop();
}
}
}
}
编辑于 2021-10-18 10:46:14
回复(0)
//用链表来模拟栈，同时链表中的节点存储最小值
import java.util.*; public class Main{ public static void main(String[] args){ MinStack minStack= new MinStack(); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i <= n; i++) { String[] op = sc.nextLine().split(" "); switch (op[0]) { case "push" : minStack.push(Integer.valueOf(op[1])); break; case "getMin": System.out.println(minStack.getMin()); break; case "pop": minStack.pop(); break; default: break; } } } } class Node{ int val; int min; Node next; public Node(int val,int min){ this.val = val; this.min = min; } } class MinStack{ Node root; void push(int val){ if (isEmpty()) { root = new Node(val,val); return; } Node node = new Node(val,root.min > val ? val : root.min); node.next = root; root = node; } //只需要后移一个节点 void pop(){ if (isEmpty()) { return; } root = root.next; } boolean isEmpty(){ return root == null; } int getMin() { if (root == null) { return -1; } return root.min; } }
发表于 2021-04-16 10:30:49
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
// 设计一个有getMin功能的栈
public class Main {
//stackData用于正常栈的功能，stackMin用于同步存储每一步的最小值
private Stack<Integer> stackData;
private Stack<Integer> stackMin;
// public构造方法
public Main(){
this.stackData = new Stack<>();
this.stackMin = new Stack<>();
}
public void push(int newNum){
if(this.stackMin.isEmpty()){
this.stackMin.push(newNum);
}else if(newNum <= this.top()){
this.stackMin.push(newNum);
}
this.stackData.push(newNum);
}
public int pop(){
if(this.stackData.isEmpty()){
throw new RuntimeException("Your stack is empty.");
}
int value = this.stackData.pop();
if(value == this.top()){
this.stackMin.pop();
}
return value;
}
public int top() {
return this.stackMin.peek();
}
public void getMin(){
if (this.stackMin.isEmpty()){
throw new RuntimeException("Your stack is empty");
}
// 这里要输出，不能return，再增加一个top，用于上面push和pop的比较
System.out.println(this.stackMin.peek());
}
public static void main(String[] args) throws IOException {
// 记得new这个类
Main m = new Main();
BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
// 读进来的String要转成Integer
int rows = Integer.parseInt(scanner.readLine());
for (int i = 0;i <rows;i++){
// 字符串空格隔开后放进数组！一个数组存放一组操作
String[] inputData = scanner.readLine().split(" ");
if(inputData[0].equals("push")){
m.push(Integer.parseInt(inputData[1]));
}
if (inputData[0].equals("pop")){
m.pop();
}
if (inputData[0].equals("getMin")){
m.getMin();
}
}
// 关！
scanner.close();
}
}
发表于 2020-03-29 18:27:00
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-01-03 10:28:29 -
2022-10-09 14:28:45
-
2022-10-08 21:48:15 -
2022-09-14 22:36:38
-
2022-09-13 15:31:22
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
