数据结构OJ:最小栈

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

OJ链接

简而言之,题目就是要我们实现一个栈,这个栈能够快速查找最小值,要求时间复杂度O(1),也就是说不能循环暴力查找

思路:

也许很多人一看到这个题目就有思路,就是定义一个min变量,入栈的时候如果元素比min小就更新min

但是这么做会有一个问题,如果最小值被pop怎么办呢?

我们会想让min回到之前的值,之前应该定义一个min_prev变量储存min之前的值,但是这只能保证min只是被pop一次,被pop多次就失效了

所以我们需要记录min的改变历程,即保证min总是能回到之前的值

我们创建一个辅助栈

数据结构OJ:最小栈,数据结构OJ,数据结构,算法

 每次向栈里push时就向辅助栈里push当前最小值,获取最小值时取辅助栈顶元素就可以,这样就实现了O(1)时间复杂度查找最小值

typedef struct {
    int* arr;
    int top;
    int capacity;
}stack;
typedef struct {
    stack s1;
    stack s2;
} MinStack;
void StackInit(stack* s)
{
    assert(s);
    s->arr = NULL;
    s->top = 0;
    s->capacity = 0;
}
void StackPush(stack* s, int x)
{
    assert(s);
    if (s->top == s->capacity)
    {
        int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2;
        s->arr = (int*)realloc(s->arr, sizeof(int) * newcapacity);
        s->capacity = newcapacity;
    }
    s->arr[s->top++] = x;
}
int StackTop(stack* s)
{
    return s->arr[s->top - 1];
}
void StackPop(stack* s)
{
    assert(s);
    s->top--;
}
void StackDestroy(stack* s)
{
    assert(s);
    free(s->arr);
}
MinStack* minStackCreate() {
    MinStack* newstack = (MinStack*)malloc(sizeof(MinStack));
    StackInit(&newstack->s1);
    StackInit(&newstack->s2);
    return newstack;
}

void minStackPush(MinStack* obj, int val) {
    StackPush(&obj->s1, val);
    if ((obj->s1).top == 1)
    {
        StackPush(&obj->s2, val);
    }
    else
    {
        if (StackTop(&obj->s2) > val)
            StackPush(&obj->s2, val);
        else
            StackPush(&obj->s2, StackTop(&obj->s2));
    }
}
void minStackPop(MinStack* obj) {
    StackPop(&obj->s1);
    StackPop(&obj->s2);
}

int minStackTop(MinStack* obj) {
    return StackTop(&obj->s1);
}

int minStackGetMin(MinStack* obj) {
    return StackTop(&obj->s2);
}

void minStackFree(MinStack* obj) {
    StackDestroy(&obj->s1);
    StackDestroy(&obj->s2);
    free(obj);
}

 文章来源地址https://www.toymoban.com/news/detail-670031.html

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

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

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

相关文章

  • 0302Prim算法-最小生成树-图-数据结构和算法(Java)

    1.1 概述 1.1.1 算法描述 算法描述: 初始化最小生成树,只有一个起点; 每次将下一条连接树中顶点和其补集中顶点且权重最小的边(黑色表示)加入树中; 重复步骤中2,直至最小生成树中加入了V-1条边。 命题L。Prim算法能够得到任意加权连通图的最小生成树。 证明:有命

    2023年04月16日
    浏览(40)
  • 数据结构与算法课程设计---最小生成树的应用

    1.问题 假定有这么一个问题,有11个城市,城市之间有一些天然气管道,铺设天然气管道需要花费不同的金额,现在要你选择其中一些天然气管道,使得所有城市可以互相联通且花费最小。 2.分析 我们把这个问题抽象为一张图,每个城市是一个顶点,城市与城市之间的管道是

    2024年02月08日
    浏览(51)
  • 【数据结构与算法】图的搜索——广度优先遍历、最小生成树

    邻接链表: 用字典实现.有向图的邻接链表的总长度等于图的边个数;无向图的邻接链表的总长度等于图的边个数的2倍. 邻接矩阵:用于最短路径算法. 该数据结构维护一个不相交动态集的集合,每个集合有一个代表,不关心谁做代表。 支持三种操作: MAKE_SET(x) FIND_SET(x) UNION(x,y

    2024年02月19日
    浏览(49)
  • C++数据结构——习题6-5 最小生成树(Prim算法)

    省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可)。已知村庄数N和可建道路数M,设初始状态下任意村庄之间没有路,请编写程序,根据输入的两村庄间修建道路的费用情况,计算这些村庄

    2024年02月09日
    浏览(79)
  • 【数据结构】无向图的最小生成树(Prime,Kruskal算法)

    连通图 :在 无向图 中,若从顶点v1到顶点v2有路径,则称顶点v1与顶点v2是连通的。如果图中 任意一对顶点都是连通的 ,则称此图为连通图 强连通图 :在 有向图 中,若在每一对顶点vi和vj之间都存在一条从vi到vj的路径,也存在一条从vj到vi的路径,则称此图是强连通图 生成

    2024年01月24日
    浏览(47)
  • 数据结构(Java)最小生成树(普里姆、克鲁斯卡尔算法)

    最小生成树 (Minimum Cost Spanning Tree) ,简称 MST 。 1) 给定一个带权的无向连通图 , 如何选取一棵生成树 , 使树上所有 边上权的总和为最小 ,就 叫最小生成树 2) N 个顶点,一定有 N-1 条边 3) 包含全部顶点 4) N-1 条边都在图中 (好像不能形成闭合回路) 求最小生成树的算法主要是

    2023年04月08日
    浏览(38)
  • java数据结构与算法刷题-----LeetCode209. 长度最小的子数组

    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完): https://blog.csdn.net/grd_java/article/details/123063846 解题思路 代码:时间复杂度O(n).空间复杂度O(1)

    2024年01月21日
    浏览(48)
  • 【数据结构与算法】最小生成树之普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

      🌱博客主页:大寄一场. 🌱系列专栏:数据结构与算法 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注 目录 前言 一、最小生成树的概念 二、最小生成树的求解方法 三、练习题 四、最小生成树在实际应用中的例子 最近非科班的同学学到了最小生成树并询问我,于是想趁

    2024年02月07日
    浏览(41)
  • 数据结构---最小生成树((普里姆算法)C语言看了就懂教程)

        普里姆算法就是“加点法”,是一种将连通网转换成最小生成树的一种算法     在一个连通图的所有生成树中,各边代价之和最小的那颗生成树称为该连通图的最小代价生成树(MST)     ①对于任意一张连通图,假设 N = (V,E)是连通网,TE就是最小生成树中边的集合    

    2024年02月03日
    浏览(45)
  • 数据结构与算法之二叉树: Leetcode 111. 二叉树的最小深度 (Typescript版)

    二叉树的最小深度 https://leetcode.cn/problems/minimum-depth-of-binary-tree/ 描述 就 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 示例 1 示例 2 提示 树中节点数的范围在 [0, 1 0 5 10^5 1 0 5 ] 内

    2024年02月06日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包