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;}

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

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

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【新版】软考 - 系统架构设计师（总结笔记）

【新版】软考 - 系统架构设计师（总结笔记）

个人总结学习笔记&#xff0c;仅供参考&#xff01;&#xff01;&#xff01;! →点击 笔者主页&#xff0c;欢迎关注哦&#xff08;互相学习&#xff0c;共同成长&#xff09; 笔记目录 &#x1f4e2;【系统架构设计系列】系统架构设计专业技能 计算机组成与结构操作系统信…
阅读更多...
【Java探索之旅】我与Java的初相识(完)：注释，标识符，关键字

【Java探索之旅】我与Java的初相识(完)：注释，标识符，关键字

&#x1f3a5; 屿小夏 &#xff1a; 个人主页 &#x1f525;个人专栏 &#xff1a; Java入门到精通 &#x1f304; 莫道桑榆晚&#xff0c;为霞尚满天&#xff01; 文章目录 &#x1f4d1;前言一. Java的注释方式二. 标识符三. 关键字四. 全篇总结 &#x1f4d1;前言 在Java编程…
阅读更多...
vue2 之 实现pdf电子签章

vue2 之 实现pdf电子签章

一、前情提要 1. 需求 仿照e签宝&#xff0c;实现pdf电子签章 > 拿到pdf链接&#xff0c;移动章的位置&#xff0c;获取章的坐标 技术 : 使用fabric pdfjs-dist vuedraggable 2. 借鉴 一位大佬的代码仓亏 : 地址 一位大佬写的文章 &#xff1a;地址 3. 优化 在大佬的代码…
阅读更多...
QT中网络编程之发送Http协议的Get和Post请求

QT中网络编程之发送Http协议的Get和Post请求

文章目录 HTTP协议GET请求POST请求QT中对HTTP协议的处理1.QNetworkAccessManager2.QNetworkRequest3.QNetworkReply QT实现GET请求和POST请求Get请求步骤Post请求步骤 测试结果 使用QT的开发产品最终作为一个客户端来使用&#xff0c;很大的一个功能就是要和后端服务器进行交互…
阅读更多...
【mongoose】 Model.create() no longer accepts a callback 报错解决

【mongoose】 Model.create() no longer accepts a callback 报错解决

在最新版的 mongoose 操作 MongoDB 数据库的时候&#xff0c;当我们插入一条数据时候&#xff0c;会报错 &#xff1a;Model.create() no longer accepts a callback&#xff0c;看了很多文章都说是&#xff0c;版本太高&#xff0c;都妥协选择了降低回旧版本&#xff0c;但我就…
阅读更多...
从0开始学会nvm管理工具（node卸载，nvm安装以及使用）

从0开始学会nvm管理工具（node卸载，nvm安装以及使用）

NVM管理工具 一、nvm介绍 在工作中&#xff0c;我们可能同时在进行2个或者多个不同的项目开发&#xff0c;每个项目的需求不同&#xff0c;进而不同项目必须依赖不同版本的NodeJS运行环境&#xff0c;这种情况下&#xff0c;对于维护多个版本的node将会是一件非常麻烦的事情&…
阅读更多...
Unity | HybridCLR 热更新（Windows端）

Unity | HybridCLR 热更新（Windows端）

目录 一、准备工作 1.环境相关 2.Unity中配置 二、热更新 1.创建 HotUpdate 热更新模块 2.安装和配置HybridCLR 3.配置PlayerSettings 4.创建热更新相关脚本 5.打包dll 6.测试热更新 一、准备工作 1.环境相关 安装git环境。Win下需要安装visual studio 2019或更高版…
阅读更多...
超维空间S2无人机使用说明书——21、VINS视觉定位仿真

超维空间S2无人机使用说明书——21、VINS视觉定位仿真

引言&#xff1a;为了实现室内无人机的定位功能&#xff0c;S系列无人机配置了VINS-FUSION定位环境&#xff0c;主要包含了仿真跑数据集和实际操作部分。为了提前熟悉使用原理&#xff0c;可以先使用仿真环境跑数据集进行学习和理解 硬件&#xff1a;1080P显示器、Jetson orin…
阅读更多...
LabVIEW与PID在温度测控系统中的应用

LabVIEW与PID在温度测控系统中的应用

LabVIEW与PID在温度测控系统中的应用 本案例介绍LabVIEW在温度控制系统中的应用&#xff0c;特别是结合PID算法。项目使用abVIEW作为主要开发工具&#xff0c;配合NI PCI-7831R数据采集和控制设备&#xff0c;实现了高效的温度调节。 系统的核心在于LabVIEW的FPGA模块&#x…
阅读更多...
【大模型实践】基于文心一言的对话模型设计

【大模型实践】基于文心一言的对话模型设计

文心一言&#xff08;英文名&#xff1a;ERNIE Bot&#xff09;是百度全新一代知识增强大语言模型&#xff0c;文心大模型家族的新成员&#xff0c;能够与人对话互动、回答问题、协助创作&#xff0c;高效便捷地帮助人们获取信息、知识和灵感。文心一言从数万亿数据和数千亿知识…
阅读更多...
探索 HTTP 请求的世界：get 和 post 的奥秘(上)

探索 HTTP 请求的世界：get 和 post 的奥秘(上)

&#x1f90d; 前端开发工程师&#xff08;主业&#xff09;、技术博主&#xff08;副业&#xff09;、已过CET6 &#x1f368; 阿珊和她的猫_CSDN个人主页 &#x1f560; 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 &#x1f35a; 蓝桥云课签约作者、已在蓝桥云…
阅读更多...
leetcode 268. 丢失的数字（优质解法）

leetcode 268. 丢失的数字（优质解法）

链接&#xff1a;268. 丢失的数字 代码: class Solution {public int missingNumber(int[] nums) {int result0;for(int i0;i<nums.length;i){result^i;}for(int i0;i<nums.length;i){result^nums[i];}return result;} } 题解&#xff1a; 本题是比较简单的题&#xff…
阅读更多...
LuaTable转C#的列表List和字典Dictionary

LuaTable转C#的列表List和字典Dictionary

LuaTable转C#的列表List和字典Dictionaty 介绍lua中创建表测试lua中list表表转成List表转成Dictionary 键值对表表转成Dictionary 多类型键值对表表转成Dictionary 总结 介绍 之前基本都是从C#中的List或者Dictionary转成luaTable&#xff0c;很少会把LuaTable转成C#的List或者…
阅读更多...
sqlilabs第三十二关

sqlilabs第三十二关

Less-32&#xff08;GET - Bypass custom filter adding slashes to dangerous chars) 手工注入 由 宽字符注入可知payload 成功触发报错 http://192.168.21.149/Less-32/ ?id1%df 要写字符串的话直接吧字符串变成ascii码 注意16进制的表示方式 自动注入 sqlmap -u http:…
阅读更多...
如何从 Android 手机免费恢复已删除的通话记录/历史记录？

如何从 Android 手机免费恢复已删除的通话记录/历史记录？

有一个有合作意向的人给我打电话&#xff0c;但我没有接听。更糟糕的是&#xff0c;我错误地将其删除&#xff0c;认为这是一个骚扰电话。那么有没有办法从 Android 手机恢复已删除的通话记录呢&#xff1f;” 塞缪尔问道。如何在 Android 上恢复已删除的通话记录&#xff1f;如…
阅读更多...
BP网络识别26个英文字母matlab

BP网络识别26个英文字母matlab

wx供重浩&#xff1a;创享日记 对话框发送&#xff1a;字母识别 获取完整源码源工程文件 一、 设计思想 字符识别在现代日常生活的应用越来越广泛&#xff0c;比如车辆牌照自动识别系统&#xff0c;手写识别系统&#xff0c;办公自动化等等。本文采用BP网络对26个英文字母进行…
阅读更多...
C# 判断两个时间段是否重叠

C# 判断两个时间段是否重叠

public static bool IsOverlap(DateTime startTime1, DateTime endTime1, DateTime startTime2, DateTime endTime2){// 判断两个时间段是否有重叠return !(endTime1 < startTime2 || startTime1 > endTime2);//根据德摩根定律&#xff0c;等效为&#xff1a;endTime1 &g…
阅读更多...
Flutter基建 - 12种隐式动画小组件全解析

Flutter基建 - 12种隐式动画小组件全解析

本篇基于Flutter 3.16.4&#xff0c;Dart 3.2.3版本 Flutter 3.16.4 • channel stable • Framework • revision 2e9cb0aa71 (3 days ago) • 2023-12-11 14:35:13 -0700 Engine • revision 54a7145303 Tools • Dart 3.2.3 • DevTools 2.28.4 本篇为Flutter基建的第九篇文…
阅读更多...
互联网上门洗衣洗鞋小程序优势有哪些？

互联网上门洗衣洗鞋小程序优势有哪些？

互联网洗鞋店小程序相较于传统洗鞋方式&#xff0c;具有以下优势&#xff1b; 1. 便捷性&#xff1a;用户只需通过手机即可随时随地下单并查询&#xff0c;省去了许多不必要的时间和精力。学生们无需走出宿舍或校园&#xff0c;就能轻松预约洗鞋并取件。 2. 精准定位&#xff1…
阅读更多...
TLC5615实现示波器波形显示——方波、三角波、锯齿波

TLC5615实现示波器波形显示——方波、三角波、锯齿波

代码&#xff1a; #include <reg52.h>sbit SCLK P2^0; // sbit&#xff1a;为寄存器的某位取名 sbit CS P2^1; sbit DIN P2^2;sbit key1 P1^0; sbit key2 P1^1; sbit key3 P1^2; sbit key4 P1^3;unsigned char rect; void delay(unsigned char i) {while(i--); }…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023