剑指offer包含min函数的栈Java

9次阅读

共计 1060 个字符,预计需要花费 3 分钟才能阅读完成。

1. 题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的 min 函数(时间复杂度应为 O(1))。


2. 思路

题目提供了一个 Stack 类让我们用,所以可以 new 一个该类的对象,这样栈的压栈、弹栈和返回顶部最大值的方法就可以直接调用 Stack 类的了。
问题的关键就是 min 函数,并且要求时间复杂度为 O(1)。
可以再使用一个 Stack 对象,只要往栈中压入一个元素,就把该元素和目前栈中最小值元素进行比较,如果更小,就把压入的元素添加到记录最小值元素的栈中,否则就把记录最小值栈的栈顶元素再压一次。如果栈进行了弹栈操作,那么记录最小值元素的栈同样也进行弹栈操作即可,min 函数就是将记录最小值元素的栈栈顶元素返回即可,但是不要弹出。

简单讲就是两个栈 A 栈记录数据,B 栈记录 A 栈中的最小值,A 栈加一个数,就比较一次,较小的加入 B 栈中,A 栈取出一个数据,B 栈也取出栈顶数据,保证两个栈的数据量相同,如果向获取 A 栈中的最小值,就获取 B 栈的栈顶元素。


3.Code

import java.util.Stack;

public class Solution {Stack<Integer> s = new Stack<>();    // 调用 Java 自带的栈对象
    Stack<Integer> minStack = new Stack<>();    // 在定义一个栈,用来存储当前 s 栈中的最小值
    int minValue = Integer.MAX_VALUE;    // 定义一个变量,用来记录当前的最小值,初始值设为 Integer 的最大值。public void push(int node) {    // 压栈方法
        s.push(node);    // 直接调用 s 的 push 方法,将元素压入栈中。if(node < minValue){    // 如果进栈的元素小于当前的最小值就把进栈元素的值赋值该 minValue。minValue = node;    // 赋值操作
        }
        minStack.push(minValue);    // 将当前的最小值压入 minStack 栈中。}
    
    public void pop() {    // 弹栈方法
        s.pop();    // 直接调用 s 的 pop 方法
        minStack.pop();    //minStack 也相应的弹出最顶的元素,保证 minStack 和 s 的元素数量一致。}
    
    public int top() {    // 查询最顶部的元素
        return s.peek();    // 直接调用 s 的 peek 方法}
    
    public int min() {    // 获取当前 s 栈中的最小值
        return minStack.peek();    // 直接将 minStack 的最顶部的元素返回即可。}
}

正文完
 0