剑指offer包含min函数的栈Java

jiezi

5 年前

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

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

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

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 的最顶部的元素返回即可。}
}

剑指offer包含min函数的栈Java

1. 题目描述

2. 思路

3.Code