面试算法:计算堆栈当前元素的最大值

面试算法:计算堆栈当前元素的最大值

有一道堆栈相关算法题,我被面试过两次以上,看似其在算法面试中出现的概率很高,由此值得我们好好分析下。题目是这样的:

对于堆栈的常用操作有, pop 弹出堆栈顶部的元素;push 向堆栈压入一个元素;peek 获得堆栈顶部的元素值,但不弹出堆栈。现在要去你增加一个操作max, 它的作用是返回堆栈当前所有元素中值最大的那个,例如堆栈当前元素有:

stack: 5,4,2,3

那么max() 返回的值就是5. 假设向堆栈继续推入元素后,情况如下:

stack: 5, 4, 2, 3, 6, 1, 10, 8

那么调用max() 得到的元素为10.

假设我们现在我们采取pop操作,弹出顶部两个元素,那么堆栈情况如下:

stack: 5, 4, 2, 3, 6, 1

显然此时max 操作返回的元素是6。

请给出一个时间复杂度为O(1)的算法,实现max操作。

这道题一个麻烦处在于,如果堆栈仅仅是压入元素,那么返回最大值是很容易的,只要把当前压入元素的最大值记下来就可以了。问题在于,堆栈还有弹出操作,当弹出后,堆栈当前的最大元素可能就会不断的发生变化。如果是压入操作和弹出操作交替进行的话,那么情况就更复杂了。

面试算法:计算堆栈当前元素的最大值

解决这个问题的算法如下:

1, 每次压入元素是,用一个变量maxVal, 记录堆栈当前元素的最大值。

2, 创建一个新堆栈maxStack,当压入元素的值大于当前元素的最大值时,把该元素压入maxStack.

3, 弹出一个元素时,如果弹出的元素是当前最大值,那么把maxStack顶部的元素也弹出,然后把maxValue设置成maxStack的顶部元素。

4,执行max()操作时,可以直接返回maxValue, 或是maxStack堆栈的顶部元素。

不难看出,上述操作使得元素压入时,maxValue 与 maxStack顶部元素保持一致,当元素弹出时,如果弹出的是当前最大值,那么步骤3把maxValue的值设置成maxStack的顶部元素,因此,无论是压入还是弹出操作,maxValue与maxStack的始终保持一致。

同时,当只有压入元素大于当前堆栈元素的最大值时,新元素才会压入maxStack,这就保证了maxStack堆栈顶部的元素就是当前堆栈中所有元素最大的一个。

上面算法,执行max()操作时,只需要把maxStack顶部元素弹出或直接返回maxValue,因此时间复杂度是O(1), 在特殊情况下,例如所有元素是升序压入堆栈的,比如压入的元素为:1,2, 3, 4.那么这些元素除了压入正常堆栈外,还得全部压入maxStack, 因此算法的空间复杂度是O(N).

我们看看具体代码的实现:

import java.util.Stack;
public class MaxStack {
 private Stack<Integer> stack = new Stack<Integer>();
 private int maxVal = Integer.MIN_VALUE;
 private Stack<Integer> maxStack = new Stack<Integer>();
 
 public void push(int val) {
 if (val >= maxVal) {
 maxVal = val;
 maxStack.push(maxVal);
 }
 
 stack.push(val);
 }
 
 public int peek() {
 return stack.peek();
 }
 
 public int pop() {
 if (stack.peek() == maxVal) {
 maxStack.pop();
 }
 
 maxVal = maxStack.peek();
 
 return stack.pop();
 }
 
 public int max() {
 return maxStack.peek();
 }
}

代码实现简单,基本上根据算法步骤来实现,我们再看看主入口处的代码:

public class StackAndQuque {

public static void main(String[] args) {

MaxStack ms = new MaxStack();

ms.push(5);

ms.push(4);

ms.push(2);

ms.push(3);

System.out.println("Max Val in stack is : " + ms.max());

ms.push(6);

ms.push(1);

ms.push(10);

ms.push(8);

System.out.println("Max Val in stack is : " + ms.max());

ms.pop();

ms.pop();

System.out.println("Max Val in stack is : " + ms.max());

ms.push(7);

System.out.println("Max Val in stack is : " + ms.max());

}

}

运行结果如下:

Max Val in stack is : 5
Max Val in stack is : 10
Max Val in stack is : 6
Max Val in stack is : 7

稍微检测下便可以发现,代码给出的结果是正确的

面试算法:计算堆栈当前元素的最大值

相关推荐