最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

经典面试题34_栈的最小值解法思路

XAMPP相关 admin 655浏览 0评论

来源:LeetCode

难度:简单

描述:

请设计一个栈,除了常规栈支持的pop与push函数以外,还支持min函数,该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

 

示例1:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   –> 返回 -3.
minStack.pop();
minStack.top();      –> 返回 0.
minStack.getMin();   –> 返回 -2.

分析:

这是一道数据结构设计题,其实就是让我们对栈增加返回最小值的功能。

由于题目要求push、pop和min操作的时间复杂度必须为O(1),因此我们不能在需要最小值的时候,再做排序、查找等操作来获取。

对于O(1),最常见的肯定是空间换时间的方法,提前将最小值存储下来,使用的时候直接返回。此处介绍两种方法,如下

 

解题

方法一:双栈法

思路:

采用两个栈,一个栈正常存放元素,另一个栈存放当前元素的最小值,和上一个栈中的元素一一对应

元素入栈时,主栈直接入栈,小栈需比较当前入栈元素和小栈栈顶元素那个小,再次入栈较小的那个元素即可,出栈时主栈和小栈同时出栈,获取当前栈的最小值即是小栈的栈顶

代码:

 1Stack<Integer> masterStack;
 2Stack<Integer> minStack;
 3
 4public MinStack() {
 5    masterStack = new Stack<>();
 6    minStack = new Stack<>();
 7}
 8
 9public void push(int x) {
10    //主栈直接入栈元素
11    masterStack.push(x);
12
13    //小栈为空时  直接入栈
14    if (minStack.isEmpty()) {
15        minStack.push(x);
16    } else {
17        //不为空,当前元素与小栈栈顶元素进行比较 入栈较小的那个
18        minStack.push(Math.min(minStack.peek(), x));
19    }
20}
21
22public void pop() {
23    //同时出栈
24    masterStack.pop();
25    minStack.pop();
26}
27
28public int top() {
29    return masterStack.peek();
30}
31
32public int getMin() {
33    //最小元素就是小栈栈顶元素
34    return minStack.peek();
35}

方法二:单栈法

思路:

方法一额外用了一个辅助栈来存储最小元素,其实用一个栈也可以实现

入栈时,先判断栈顶元素和待入栈元素大小,用临时变量记录较小的那个,再将待入栈元素入栈,并将临时变量记录的小元素也入栈

出栈时,需连续出两次,因为入栈时将元素和最小值同时入栈了

最小值即是栈顶元素

本方法相当于将方法一中的最小栈和主栈融合到一起了

 

代码:

 1Stack<Integer> masterStack;
 2
 3public MinStack() {
 4    masterStack = new Stack<>();
 5}
 6
 7public void push(int x) {
 8
 9    //为空直接入两次即可
10    if (masterStack.isEmpty()) {
11        masterStack.push(x);
12        masterStack.push(x);
13    } else {
14        //不为空,记录栈顶和当前元素较小的那个,先入当前元素,再入较小的那个
15        int temp = Math.min(masterStack.peek(), x);
16        masterStack.push(x);
17        masterStack.push(temp);
18    }
19}
20
21public void pop() {
22    //出栈两次
23    masterStack.pop();
24    masterStack.pop();
25}
26
27public int top() {
28    //实际元素在栈顶的下一个位置,因此出栈栈顶最小值
29    // 记录真实元素后,再将最小值入栈,返回真实元素即可
30    int min = masterStack.pop();
31    int real = masterStack.peek();
32    masterStack.push(min);
33    return real;
34}
35
36public int getMin() {
37    //最小元素就是小栈栈顶元素
38    return masterStack.peek();
39}

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 经典面试题34_栈的最小值解法思路

您必须 登录 才能发表评论!