题解 | #包含min函数的栈#

包含min函数的栈

https://www.nowcoder.com/practice/4c776177d2c04c2494f2555c9fcc1e49

思路

本题难点在于栈中最小值该怎么记录,我们可以创建一个最小值栈,记得默认栈入栈第一个元素要入最小栈,接着判断当前入栈元素是否小于等于最小栈栈顶元素,如果满足条件则将其加入最小栈,当弹出元素时,需要判断弹出值是否为最小栈栈顶元素,如果是,也需要同时弹出。

代码

import java.util.Stack;

public class Solution {


    /**
     * 最小值栈
     */
    Stack<Integer> minimumStack = new Stack<>();
    /**
     * 主栈
     */
    Stack<Integer> mainStack = new Stack<>();

    /**
     * 普普通通push方法
     *
     * @param node 元素
     * @apiNote 将value压入栈中
     * @since 2023/1/7 19:06
     */
    public void push(int node) {
        // 判断最小值栈是否为空
        if (mainStack.isEmpty()) {
            minimumStack.push(node);
        } else {
            // 如果最小值栈中栈顶元素大于等于输入元素,将该元素加入最小值栈中
            if (minimumStack.peek() >= node) {
                minimumStack.push(node);
            }
        }
        mainStack.push(node);
    }

    /**
     * 普普通通pop方法
     *
     * @apiNote 弹出栈顶元素
     * @since 2023/1/7 19:12
     */

    public void pop() {
        // 判断主栈是否为空,为空不执行方法
        if (mainStack.isEmpty()) {
            return;
        }
        // 判断出栈元素是否为当前最小值,如果是则在主栈弹出元素的同时最小值栈也弹出元素
        if (mainStack.pop().equals(minimumStack.peek())) {
            minimumStack.pop();
        }
    }

    /**
     * 普普通通top方法
     *
     * @return int
     * @apiNote 获取栈顶元素
     * @since 2023/1/7 19:15
     */
    public int top() {
        return mainStack.peek();
    }

    /**
     * 普普通通min方法
     *
     * @return int
     * @apiNote 获取栈中最小元素
     * @since 2023/1/7 19:16
     */
    public int min() {
        return minimumStack.peek();
    }
}
全部评论

相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务