LeetCode 面试题 03.02. 栈的最小值

这篇具有很好参考价值的文章主要介绍了LeetCode 面试题 03.02. 栈的最小值。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、题目

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

  点击此处跳转题目。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

二、C# 题解

  要实现 O(1) 复杂度的 min 函数,只需多使用一个数组记录最小值即可:文章来源地址https://www.toymoban.com/news/detail-693930.html

public class MinStack {
    private List<int> data; // 存放栈数据
    private List<int> mins; // 存放对应栈的最小值

    private int p;          // 栈顶指针

    /** initialize your data structure here. */
    public MinStack() {
        data = new List<int>(128);
        mins = new List<int>(128);
        p = -1;
    }
    
    public void Push(int x) {
        data.Add(x);
        if (p == -1) mins.Add(x);
        else mins.Add(x < mins[p] ? x : mins[p]); // 比较 x 与 min,放入更小的一个
        p++;
    }
    
    public void Pop() {
        if (p == -1) return;
        data.RemoveAt(p);
        mins.RemoveAt(p);
        p--;
    }
    
    public int Top() {
        return data[p];
    }
    
    public int GetMin() {
        return mins[p];
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.Push(x);
 * obj.Pop();
 * int param_3 = obj.Top();
 * int param_4 = obj.GetMin();
 */
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)

到了这里,关于LeetCode 面试题 03.02. 栈的最小值的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode 面试题 03.04. 化栈为队

      实现一个MyQueue类,该类用两个栈来实现一个队列。   点击此处跳转题目。 示例: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false 说明: 你只能使用标准的栈操作 – 也就是只有 push to top , peek/pop from top , s

    2024年02月09日
    浏览(39)
  • LeetCode 面试题 02.08. 环路检测

      给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。若环不存在,请返回 null 。   如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索

    2024年02月10日
    浏览(34)
  • leetcode 面试题 02.02. 返回倒数第k个节点

    提建议就是,有些题还是有联系的,建议就收看完  876.链表的中间节点( ) ,再将这一题联系起来 题目: 实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。 说明: 给定的 k 保证是有效的。 题目链接 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 文

    2024年02月04日
    浏览(37)
  • LeetCode 面试题 02.02. 返回倒数第 k 个节点

      实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。   注意:本题相对原题稍作改动   点击此处跳转题目。 示例: 输入: 1-2-3-4-5 和 k = 2 输出: 4 说明: 给定的 k 保证是有效的。   先遍历一遍求总结点数 n,再顺序寻找第 n - k + 1 个节点就可以了

    2024年02月11日
    浏览(39)
  • leetcode 面试题 02.07. 链表相交

    题目:leetcode 面试题 02.07. 链表相交 描述: 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。 图示两个链表在节点 c1 开始相交: 思路: 简单来说,就是求两个链表交点节点的指针。 这里要注意,交点

    2024年02月13日
    浏览(40)
  • LeetCode 面试题 02.04. 分割链表

      给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。   你不需要 保留 每个分区中各节点的初始相对位置。   点击此处跳转题目。 示例 1: 输入:head = [1,4,3,2,5,2], x = 3 输出:[1,2,2,4,3,5] 示例

    2024年02月11日
    浏览(38)
  • leetcode 面试题 02.05 链表求和

    🌟 leetcode链接:面试题 02.05 链表求和 ps: 首先定义一个头尾指针 head 、 tail ,这里的 tail 是方便我们尾插,每次不需要遍历找尾,由于这些数是反向存在的,所以我们直接加起来若大于等于 10 则进位,进位的数字加到下一位的数字和上,需要注意的是,当任意一个链表结束

    2024年02月12日
    浏览(39)
  • LeetCode 面试题 02.01. 移除重复节点

      编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。   点击此处跳转题目。 示例1: 输入:[1, 2, 3, 3, 2, 1] 输出:[1, 2, 3] 示例2: 输入:[1, 1, 1, 1, 2] 输出:[1, 2] 提示: 链表长度在[0, 20000]范围内。 链表元素在[0, 20000]范围内。 进阶: 如果不得使用临时缓冲

    2024年02月11日
    浏览(39)
  • leetcode刷题记录:二叉树02(思路篇)

    参考labuladong的算法小抄:https://labuladong.online/algo/data-structure/binary-tree-part1/ 复习二叉树纲领篇,二叉树解题的思维模式分两类: 1、是否可以通过遍历一遍二叉树得到答案?如果可以,用一个 traverse 函数配合外部变量来实现,这叫「遍历」的思维模式。 2、是否可以定义一个

    2024年02月19日
    浏览(40)
  • LeetCode 面试题 01.02. 判定是否互为字符重排

    ​   给定两个由小写字母组成的字符串 s1 和 s2,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串,点击此处跳转。 示例 1: 输入: s1 = “abc”, s2 = “bca” 输出: true 示例 2: 输入: s1 = “abc”, s2 = “bad” 输出: false 说明: 0 = len(s1) = 100 0

    2024年02月12日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包