前言

来自程序员面试金典中的一道题目。

题目描述

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

解题思路

使用两个栈，一个是正常操作的栈，另一个则是让栈顶元素永远都是最小值的栈，这样就可以实现执行push、pop和min操作的时间复杂度都为O(1)。

1、准备两个栈stack、minStack。

2、操作元素添加x时，直接添加到stack栈中，然后再判断如果minStack栈不为空，且minStack栈顶元素的值小于x时，则minStack栈添加自己当前栈顶的元素，否则添加x。

图解分析

1、添加元素5

在这里插入图片描述

2、添加元素6，由于6大于5，所以最小值的栈还是添加5

在这里插入图片描述

3、添加元素4，4小于5，所以最小值的栈添加4。

4、添加7，同理最小值的栈添加的是4。

现在当要取栈中的最小值时，直接从记录最小值得栈顶获取即可，时间复杂度是O(1)。

代码实现

import java.util.Stack;public class MinStack {
       Stack
   
     stack;    Stack
    
      minStack;    public MinStack() {
           stack = new Stack();        minStack = new Stack();    }    public void push(int x) {
           stack.push(x);        if (minStack.size() != 0 && x > minStack.peek()) {
               minStack.push(minStack.peek());        } else {
               minStack.push(x);        }    }    public void pop() {
           stack.pop();        minStack.pop();    }    public int top() {
           return stack.peek();    }    public int getMin() {
           return minStack.peek();    }}

转载地址：http://cqlrb.baihongyu.com/

你可能感兴趣的文章