【剑指offer】-包括main函数的栈-21/67

1. 题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
注意:保证测试中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法。

2. 题目分析

该题有二种解决方法

2.1 常规解决思路:

在写min()方法的时候,建立一个辅助栈,将stack中的元素导入至辅助栈中,并且比较出来最小值,在从辅助栈导入至stack中。

2.2 剑指offer思路:

创建两个栈,分别为数据栈(stcak1)和辅助栈(stack2),每一次数据(node)储存至数据栈时,判断当前的辅助栈是否为空和node是否小于辅助栈中最小的数值(也就是栈顶的数值)。若小于,则将node压入辅助栈(作为最小值)。若大于,则将辅助栈顶的数字再一次压入。

3. 题目代码

常规思路代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Stack;

public class Solution {


Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> stack1 = new Stack<Integer>();

public void push(int node) {
stack.push(node);
}

public void pop() {
stack.pop();
}

public int top() {
return stack.peek();
}

public int min() {
int min = stack.peek();
while (stack.isEmpty() != true) {
int node = stack.pop();
if (node < min) {
min = node;
}
stack1.push(node);
}
while (stack1.isEmpty() != true) {
stack.push(stack1.pop());
}
return min;
}
}

剑指offer思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(node);//将数据保存至数据栈
//当辅助栈为空或者当前数据小于辅助栈中最小的值时 添加至辅助栈
if(stack2.isEmpty() || node < stack2.peek()) {
stack2.push(node);
}else {
stack2.push(stack2.peek());
}
}

public void pop() {
stack1.pop();
stack2.pop();
}

public int top() {
return stack1.peek();
}

public int min() {
return stack2.peek();
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信