LeetCode 热题100——单调栈

​

  个人主页：日刷百题

系列专栏：〖C语言小游戏〗〖Linux〗〖数据结构〗 〖C语言〗

🌎欢迎各位→点赞👍+收藏⭐️+留言📝 ​

​

 写在前面：

递增单调栈：栈中元素从栈底到栈顶依次增大
递减单调栈：栈中元素从栈底到栈顶依次减小

在学习完朴素的数据结构栈之后，单调栈作为栈的一种升级版应用，在某些情境下具有得天独厚的优越性：可将O(n²)的遍历复杂度降低至O(n)！

以下就是几种经典的单调栈运用问题。

一、字符串解码 

 

 思路:这题利用了栈，但不是单调栈，我们看到括号问题容易联想到有效括号问题也是利用栈

（1）遍历字符数组，当没有遇到‘]’时，将字符全部入栈

（2）若遇到‘]’，将字母一一出栈，入到临时栈，直到遇到‘[’停止

（3）此时将'['出栈，此时栈顶必然是数字字符，将数字字符全部转化为mulsize数字，出栈

（4）用2层嵌套循环，外层为mulsize,内层为临时栈的元素个数，将临时栈元素按mulszie次循环放进栈中，最后将临时栈初始化

（5）最后，字符遍历结束，栈中元素即为所求，此时将栈的末尾加上’\0’.

注：这里值得注意的地方有俩点

<1>在栈末尾插入‘\0’，得有扩容判断

<2>在将数字字符转化为mulsize时，字符数字是一个个出栈，为逆序，例如：100出栈为001，所以转化为数字的时候，要注意

typedef char DateType;
typedef struct Stack
{
    DateType* a;
    int top;
    int capacity;
}Stack;
//初始化和销毁栈
void InitStack(Stack* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
void DestoryStack(Stack* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

//出栈和入栈
void StackPush(Stack* ps, DateType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        DateType* tmp = (DateType*)realloc(ps->a, sizeof(DateType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail:");
            return;
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}
void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

//栈的有效个数和栈顶元素
int StackSize(Stack* ps)
{
    assert(ps);
    return ps->top;
}
DateType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return   ps->a[ps->top - 1];
}
//判空
bool IsEmptyStack(Stack* ps)
{
    assert(ps);
    return ps->top == 0;
}
char* decodeString(char* s) {
    Stack ps;
    Stack tmp;
    InitStack(&ps);
    InitStack(&tmp);
    int len = strlen(s);
    while ((*s) != '\0')
    {
        if ((*s) != ']')
        {
            StackPush(&ps, (*s));
        }
        else
        {
         
            while (StackTop(&ps) != '[')
            {
                char b = StackTop(&ps);
                StackPop(&ps);
                StackPush(&tmp, b);
              
            }
            StackPop(&ps);
            int tmpsize = tmp.top;
            int mulsize=0;
            int i=0;
            while (ps.top > 0 && ps.a[ps.top - 1] >= '0' && ps.a[ps.top - 1] <= '9')
            {


                mulsize =mulsize  + pow(10,i)*(ps.a[ps.top - 1] - '0');
                StackPop(&ps);
                i++;
            }
            for (int i = 0; i < mulsize; i++)
            {
                for (int j = 0; j < tmpsize; j++)
                {
                    char w = StackTop(&tmp);
                    StackPush(&ps, w);
                    StackPop(&tmp);
                }
                tmp.top = tmpsize;
            }

        }
        if (tmp.a != NULL)
        {
            free(tmp.a);
            tmp.a = NULL;
            InitStack(&tmp);
        }
        s++;
    }
    DestoryStack(&tmp);
    if (ps.top == ps.capacity)
    {
        int newcapacity = ps.capacity == 0 ? 4 : 2 * ps.capacity;
        DateType* tmp = (DateType*)realloc(ps.a, sizeof(DateType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail:");
            return 1;
        }
        ps.a = tmp;
        ps.capacity = newcapacity;
    }
    ps.a[ps.top] = '\0';
    return ps.a;
}

 二、接雨水

思路:这题思路比较巧妙，运用了单调递减栈

（1）创造栈用来存放数组元素下标

（2）遍历数组，若栈为空或者栈顶元素所对应的数组值大于等于数组元素，则直接入栈

（3）若栈顶元素所对应数组元素值小于数组元素，则做出判断，将栈顶元素保存，且出栈，再用此时的栈顶元素所对应的数组值与数组元素比较，俩个数的较小值减去原来保存的栈顶元素所对应数组值即为接雨水凹槽的高，此时数组下标与栈顶差值减1即为接雨水凹槽的宽，相乘即为所接雨水的面积，保持循环，直到栈为空或者栈为递减，退出循环，进行数组下一个元素比较。

上面思路听起来比较复杂，可以看图理解：

typedef int DateType;
typedef struct  Stack
{
    DateType* a;
    int top;
    int capacity;
}Stack;
//初始化和销毁
void InitStack(Stack* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
void DestroyStack(Stack* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
//出栈和入栈
void StackPush(Stack* ps, DateType x)
{
    assert(ps);
    if(ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 4;
        DateType* tmp = (DateType*)realloc(ps->a,sizeof(DateType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail:");
            return;
        }
        ps->capacity = newcapacity;
        ps->a = tmp;
    }
    ps->a[ps->top] = x;
    ps->top++;

}
void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}
//栈顶元素和元素个数
int StackSize(Stack* ps)
{
    assert(ps);
    return  ps->top;
}
DateType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}

//判空
bool  IsEmptyStack(Stack* ps)
{
    assert(ps);
    return ps->top == 0;
}
int MIN(int x, int y)
{
    return x > y ? y : x;
}
int trap(int* height, int heightSize) {
    Stack ps;
    InitStack(&ps);
    int count = 0;
    for (int i = 0; i < heightSize; i++)
    {
        while (ps.top > 0 && height[StackTop(&ps)] < height[i])
        {
            DateType tmp = StackTop(&ps);
            StackPop(&ps);
            if (ps.top == 0)
            {
                break;
            }
            int h = MIN(height[StackTop(&ps)], height[i]);
            int width = i - StackTop(&ps) - 1;
            count += (h - height[tmp]) * width;
        }

        StackPush(&ps, i);


    }
    DestroyStack(&ps);
    return count;
}

三、每日温度 

 

 思路:这题思路比较巧妙，运用了单调递减栈和上面一题类似

（1）创造栈用来存放数组元素下标

（2）遍历数组，若栈为空或者栈顶元素所对应的数组值大于等于数组元素，则直接入栈

（3）若栈顶元素所对应数组元素值小于数组元素，则做出判断，将栈顶元素保存，且出栈，由于当前数组元素大于栈顶元素对应数组元素值，而且一定是第一个大于栈顶元素对应数组元素值，直接求出下标差（当前数组元素下标和栈顶元素差）就是二者的距离，放入所求目标数组内（数组下标为保存的栈顶元素）。继续看新的栈顶元素，循环往复，直到当前数组元素小于等于栈顶元素所对应数组值或者栈为空停止，然后将数组元素下标入栈，进行数组下一个元素比较

（3)数组遍历结束后，栈为单调递减栈，里面元素所对应数组值（气温）向后检索找不到比它高的温度，所以以这些栈元素为下标的目标数组元素全部置为0.

图解如下：

typedef int DateType;
typedef struct  Stack
{
    DateType* a;
    int top;
    int capacity;
}Stack;
//初始化和销毁
void InitStack(Stack* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
void DestroyStack(Stack* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
//出栈和入栈
void StackPush(Stack* ps, DateType x)
{
    assert(ps);
    if(ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 4;
        DateType* tmp = (DateType*)realloc(ps->a,sizeof(DateType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail:");
            return;
        }
        ps->capacity = newcapacity;
        ps->a = tmp;
    }
    ps->a[ps->top] = x;
    ps->top++;

}
void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}
//栈顶元素和元素个数
int StackSize(Stack* ps)
{
    assert(ps);
    return  ps->top;
}
DateType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}

//判空
bool  IsEmptyStack(Stack* ps)
{
    assert(ps);
    return ps->top == 0;
}

int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {
    int *answer=(int *)malloc(sizeof(int)*temperaturesSize);
    Stack  st;
    InitStack(&st);
    for(int i=0;i<temperaturesSize;i++)
    {
        while(st.top>0&&temperatures[i]>temperatures[StackTop(&st)])
        {
                answer[StackTop(&st)]=i-StackTop(&st);
                StackPop(&st);
                if(st.top==0)
                {
                    break;
                }
                
        }
       
            StackPush(&st,i);
        
    }
    while(st.top>0)
    {
        answer[StackTop(&st)]=0;
        StackPop(&st);
    }
     * returnSize=temperaturesSize;
    return answer;
    
}

四、柱状图中最大的矩形 

 

思路:这题思路与接雨水问题一样，不过此题用的是严格单调增栈 

（1）创造栈用来存放数组元素下标

（2）遍历数组，若栈为空或者栈顶元素所对应的柱形高度小于当前柱形高度，则当前柱形高度的数组下标直接入栈

（3）若栈顶元素所对应数组元素值大于等于数组元素，则做出判断，将栈顶元素临时保存，且出栈，再用当前数组元素下标与栈顶元素做差-1即为临时保存的栈顶元素所对应柱形高度的宽，根据原来临时保存栈顶元素求出其对应的高，就可以求出该高度的最大矩形面积，，保持循环，直到栈为空或者栈为严格递增，退出循环，进行数组下一个元素比较。

（4）数组遍历结束，栈为严格单调递增栈，除了最后一个栈底元素外，其他栈元素对应柱形高度最大矩形宽度为数组长度减去当前栈元素左侧一个栈元素的值-1，栈底元素对应柱形高度最大矩形宽度为数组元素长度

注：这里面有几个注意的细节

<1>当栈元素为1个，且数组元素小于等于栈顶对应柱形高度，此时临时保存栈顶元素，出栈，此临时保存栈顶元素对应柱形高度所能扩展做大矩形宽度为：当前数组元素下标i减去临时保存的栈顶元素

<2>数组元素等于栈顶栈顶对应柱形高度时，虽然所求的最大矩形不是这个栈顶的最大矩形，但是要小于这个栈顶元素对应的最大矩形面积，不碍事，直到下一个数组元素严格小于栈顶元素对应柱形高度，此时所求的最大矩形面积即之前那个相等高度的最大矩形面积，所以不影响

图解如下：

typedef int DateType;
typedef struct  Stack
{
    DateType* a;
    int top;
    int capacity;
}Stack;
//初始化和销毁
void InitStack(Stack* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
void DestroyStack(Stack* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}
//出栈和入栈
void StackPush(Stack* ps, DateType x)
{
    assert(ps);
    if(ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 4;
        DateType* tmp = (DateType*)realloc(ps->a,sizeof(DateType) * newcapacity);
        if (tmp == NULL)
        {
            perror("realloc fail:");
            return;
        }
        ps->capacity = newcapacity;
        ps->a = tmp;
    }
    ps->a[ps->top] = x;
    ps->top++;

}
void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}
//栈顶元素和元素个数
int StackSize(Stack* ps)
{
    assert(ps);
    return  ps->top;
}
DateType StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}

//判空
bool  IsEmptyStack(Stack* ps)
{
    assert(ps);
    return ps->top == 0;
}
int  MAX(int x, int y)
{
    return x>y?x:y;
}

int largestRectangleArea(int* heights, int heightsSize) {
    Stack st;
   InitStack(&st);
    int max = 0;
   
    for (int i = 0; i < heightsSize; i++)
    {
        while (st.top>0 && heights[i] <= heights[StackTop(&st)])
        {
            int tmp = StackTop(&st);
            StackPop(&st);
            if(st.top==0)
            {
                max=MAX(max, heights[tmp]*i);
                break;
            }
            int width = i - StackTop(&st) - 1;
            max = MAX(max, heights[tmp] * width);
        }

          StackPush(&st, i);//严格单调增
        
    }
    //遍历结束后，变为严格单调递增栈
    while (st.top>0)
    {
        int tmp =StackTop(&st);
        StackPop(&st);
        if (st.top==0)
        {
            max = MAX(max, heights[tmp] * heightsSize);
          break;
        }
        int width = heightsSize - StackTop(&st)-1 ;
        max = MAX(max, heights[tmp] * width);
       
    }
    return max;
   

}

 总结：本篇文章讲解了单调栈的应用，为系列题目，有利于帮助理解单调栈的用法和这系列问题思路。

希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，百题一定会认真阅读！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/261928.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

7-1 单身狗(PTA - 数据结构)

7-1 单身狗(PTA - 数据结构)

由于这道题在留的作业中&#xff0c;排序和查找都有&#xff0c;所以我先写这道题&#xff08;图的先放放&#xff09; “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人&#xff0c;以便给予特殊关爱。 输入格式&#xff1a; 输入第一行…
阅读更多...
Linux笔记---文件查看和编辑

Linux笔记---文件查看和编辑

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;Linux学习 ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 命令 cat (Concatenate and Display): more 和 less: nano 和 vim (文本编辑器): 结语 我的其他博客 前言 学习Linux命令行和文件…
阅读更多...
C++实现位图

C++实现位图

目录 一、什么是位图 二、位图类 1.参数及构造函数 2.set函数设置为1&#xff08;代表存在&#xff09; 3.reset函数设置为0&#xff08;代表不存在&#xff09; 4.test函数查看状态&#xff08;0还是1&#xff09; 三、位图的变形 一、什么是位图 位图这个词汇比较少见…
阅读更多...
im6ull学习归纳总结（一）APP——04_文件IO

im6ull学习归纳总结（一）APP——04_文件IO

4.1文件从何而来 如图所示文件可以是 1真实文件保存在设备上 2内核提供的虚拟文件 3设备节点 4.2文件的访问方式 4.2.1通用IO模型&#xff1a;open/read/write/lseek/close 实验1 copy文件 代码 #include <sys/types.h> #include <sys/stat.h> #include <fc…
阅读更多...
10 个顶级免费 Android 数据恢复软件可帮助恢复已删除的文件

10 个顶级免费 Android 数据恢复软件可帮助恢复已删除的文件

不小心删除了手机上的一些重要数据或文件&#xff1f;这很不幸&#xff0c;但不要悲伤或放弃希望&#xff0c;因为仍有机会恢复它们。 10 个顶级免费 Android 数据恢复软件 虽然 Android 手机没有像 Windows 那样的回收站可以自动存储您删除的数据&#xff0c;但是有很多功能强…
阅读更多...
大模型时代下的因果推断

大模型时代下的因果推断

导读&#xff1a;在数字化建设不断推进的今天&#xff0c;随着技术的不断发展&#xff0c;从统计学、机器学习、深度学习&#xff0c;再到因果学习&#xff0c;以及最新的热门大模型方向&#xff0c;九章云极DataCanvas始终紧贴最前沿的、最能助力企业和落地实践的方向&#xf…
阅读更多...
合伙企业的优缺点是什么

合伙企业的优缺点是什么

合伙企业的优缺点是什么 一、合伙企业的优点 合伙企业在资本扩张方面较个人独资企业更有优势。个人独资企业仅有一个投资人&#xff0c;尽管存在整个家庭财产成为个人独资企业资本来源的情形&#xff0c;但该类企业资本规模相对较小、抗风险能力较弱。为扩张资本&#xff0c;单…
阅读更多...
通过U盘：将电脑进行重装电脑

通过U盘：将电脑进行重装电脑

目录 一.老毛桃制作winPE镜像 1.制作准备 2.具体制作 下载老毛桃工具 插入U盘 选择制作模式 正式配置U盘 安装提醒 安装成功 具体操作 二.使用ultrasio制作U盘 1.具体思路 2.图片操作 三.硬盘安装系统 具体操作 示例图 ​编辑 一.老毛桃制作winPE镜像 1.制作准…
阅读更多...
基本数据类型变量间的运算规则、基本数据类型与String的运算

基本数据类型变量间的运算规则、基本数据类型与String的运算

目录 一、自动类型提升 二、强制类型转换 三、基本数据类型与String的运算 1 字符串类型&#xff1a;String 2 运算规则 在Java程序中&#xff0c;不同的基本数据类型&#xff08;只有7种&#xff0c;不包含boolean类型&#xff09;变量的值经常需要进行相互转换。转换的方…
阅读更多...
产品原型设计软件 Axure RP 9 mac支持多人写作设计

产品原型设计软件 Axure RP 9 mac支持多人写作设计

axure rp 9 mac是一款产品原型设计软件&#xff0c;它可以让你在上面任意构建草图、框线图、流程图以及产品模型&#xff0c;还能够注释一些重要地方&#xff0c;axure rp汉化版可支持同时多人写作设计和版本管理控制&#xff0c;这款交互式原型设计工具可以帮助设计者制作出高…
阅读更多...
playbook变量的使用(二)

playbook变量的使用(二)

接上一章&#xff1a; 内置变量 变量的过滤器 31.9 内置变量hostvars hostvars用来显示指定主机的 fact变量,用法如下。 1 hostvars[ 主机名 ].键值 此变量一般用于&#xff0c;当某个play的 hosts 中只写了A主机组&#xff0c;但是同时想在此play中显示B 主机组中的信息,这…
阅读更多...
Gradle中 Implementation 与API 声明依赖方式的对比

Gradle中 Implementation 与API 声明依赖方式的对比

在Gradle中&#xff0c;implementation和api是声明依赖的两种方式&#xff0c;它们在如何暴露依赖关系方面有所不同&#xff1a; Implementation: 当一个模块使用implementation声明依赖时&#xff0c;该依赖仅对声明它的模块可见。这意味着该依赖对于该模块的消费者是隐藏的。…
阅读更多...
回归预测 | MATLAB实现GWO-DHKELM基于灰狼算法优化深度混合核极限学习机的数据回归预测 （多指标，多图）

回归预测 | MATLAB实现GWO-DHKELM基于灰狼算法优化深度混合核极限学习机的数据回归预测 （多指标，多图）

回归预测 | MATLAB实现GWO-DHKELM基于灰狼算法优化深度混合核极限学习机的数据回归预测 &#xff08;多指标&#xff0c;多图&#xff09; 目录 回归预测 | MATLAB实现GWO-DHKELM基于灰狼算法优化深度混合核极限学习机的数据回归预测 &#xff08;多指标&#xff0c;多图&#…
阅读更多...
如何通过ssh管道传输文件到ubuntu

如何通过ssh管道传输文件到ubuntu

&#x1f4d1;Linux/Ubuntu 常用命令归类整理 如何在window系统中&#xff0c;通过ssh将指定的文件传输到ubuntu中呢&#xff1f; 比较常用的有以下种方式&#xff1a; 共享文件夹借助工具&#xff0c; FileZillaMobaxtermWinSCPXshell XFTP samba互传PuTTY pscp 今天主要…
阅读更多...
【Mode Management】CanSM详细介绍

【Mode Management】CanSM详细介绍

1. Introduction and functional overview AUTOSAR BSW栈为每个通信总线指定一个总线特定的状态管理器。CANSM实现CAN总线的数据流控制。CanSM隶属于通信服务层。CanSM和通信硬件抽象层以及系统服务层交互。 CanSM只用用于控制CAN通信。CanSM的任务就是操作CanIf模块去控制一个…
阅读更多...
Python中abstractmethod的使用教程

Python中abstractmethod的使用教程

更多资料获取 &#x1f4da; 个人网站&#xff1a;ipengtao.com 在Python中&#xff0c;抽象类和抽象方法提供了一种强制子类实现特定方法的机制。abstractmethod是abc&#xff08;Abstract Base Classes&#xff09;模块中的一部分&#xff0c;它允许定义抽象方法&#xff0c…
阅读更多...
阿赵UE学习笔记——3、常用界面窗口

阿赵UE学习笔记——3、常用界面窗口

阿赵UE学习笔记目录 大家好&#xff0c;我是阿赵。继续学习虚幻引擎&#xff0c;这次介绍的是编辑器的常用界面窗口。 一、视口 这个视口的概念&#xff0c;可以体现出UE对于多屏幕同时显示是多么的友好。我们开发游戏的时候&#xff0c;一般都会同一台电脑用2个或者以上显示器…
阅读更多...
Docker的安装和使用

Docker的安装和使用

目录 安装Docker 安装yum工具 更新本地镜像源 安装docker 启动docker 关闭防火墙 docker启动命令 配置镜像加速 docker的使用 拉取nginx 查看本地镜像 把镜像文件nginx导出成tar文件 查看是否导出成功 ​编辑 删除本地镜像nginx:latest 导入镜像文件nginx 拉取…
阅读更多...
算法基础之快速幂求逆元

算法基础之快速幂求逆元

快速幂求逆元 核心思想&#xff1a; 逆元&#xff1a; 逆元 ap-2 mod p #include<iostream>#include<algorithm>using namespace std;typedef long long LL;LL pmi(int a,int b,int c){LL res 1;while(b){if(b & 1) res res * a %c;b >> 1;a (LL)…
阅读更多...
java定义三套场景接口方案

java定义三套场景接口方案

一、背景 在前后端分离开发的背景下&#xff0c;后端java开发人员现在只需要编写接口接口。特别是使用微服务开发的接口。resful风格接口。那么一般后端接口被调用有下面三种场景。一、不需要用户登录的接口调用&#xff0c;第二、后端管理系统接口调用&#xff08;需要账号密…
阅读更多...
最新文章

Copyright @ 2022~2023