1. Toy模板网首页
  2. > Toy博客

LeetCode 热题100——单调栈

10月前 作者：日刷百题 分类：Toy博客 阅读(40) 违法举报

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

​

LeetCode 热题100——单调栈,LeetCode,数据结构,c++,c语言

  个人主页：日刷百题

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

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

​LeetCode 热题100——单调栈,LeetCode,数据结构,c++,c语言

 写在前面：

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

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

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

一、字符串解码 

LeetCode 热题100——单调栈,LeetCode,数据结构,c++,c语言 

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

（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即为接雨水凹槽的宽，相乘即为所接雨水的面积，保持循环，直到栈为空或者栈为递减，退出循环，进行数组下一个元素比较。

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

LeetCode 热题100——单调栈,LeetCode,数据结构,c++,c语言

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

三、每日温度 

LeetCode 热题100——单调栈,LeetCode,数据结构,c++,c语言 

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

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

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

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

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

图解如下：

LeetCode 热题100——单调栈,LeetCode,数据结构,c++,c语言

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

四、柱状图中最大的矩形 

LeetCode 热题100——单调栈,LeetCode,数据结构,c++,c语言 

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

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

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

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

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

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

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

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

图解如下：

LeetCode 热题100——单调栈,LeetCode,数据结构,c++,c语言

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;
   

}

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

希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，百题一定会认真阅读！文章来源地址https://www.toymoban.com/news/detail-764531.html

到了这里，关于LeetCode 热题100——单调栈的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀，今天继续数据结构与算法专栏中的二叉树，下面，让我们进入二叉树的世界吧！！！ 二叉树（上）——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

    2024年02月17日
    浏览(41)

  • 螺旋矩阵 LeetCode热题100

    给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。 模拟，朝一个方向走，走过的点标记一下，直到碰到边界或碰到已经走过的路，换个方向。右-下，下-左，左-上，上-右。直到走完所有点。

    2024年02月14日
    浏览(64)
  • LeetCode热题100——图论

    LeetCode热题100——图论

    给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 输入：grid = [ [“1”,“1”,“1”,“1”,“0”], [“1”,“1”,“0”,“1”,“0”], [“1”,“1”

    2024年01月16日
    浏览(76)
  • LeetCode 热题 HOT 100

    LeetCode 热题 HOT 100

    重点是当有一个链表为空了不单独处理，按节点为0处理。 滑动窗口！ 首先要判断slow需不需要更新，怎么判断？slow = max(umap[s[fast]], slow);什么意思，就是说：**umap[s[fast]]的意义是，为了在slow和fast之间不出现重复字符，slow能处于的最左位置。**如图，当j第一次到d，将umap[s[j

    2024年02月07日
    浏览(47)
  • LeetCode 热题 100 | 哈希

    LeetCode 热题 100 | 哈希

    目录 1  基础知识 1.1  定义哈希表 1.2  遍历哈希表 1.3  查找某一个键 1.4  插入键值对 1.5  获取键值对的值 1.6  搜索功能 2  三道题 2.1  1. 两数之和 2.2  49. 字母异位词分组 2.3  128. 最长连续序列 菜鸟做题第一周，语言是 C++ 1  基础知识 1.1  定义哈希表 unordered_map 用于定义

    2024年01月18日
    浏览(47)
  • LeetCode热题100——链表

    LeetCode热题100——链表

    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回

    2024年02月05日
    浏览(43)
  • LeetCode 热题 100 | 链表（上）

    LeetCode 热题 100 | 链表（上）

    目录 1  基础知识 1.1  空指针 1.2  结构体 1.3  指针访问 1.4  三目运算符 2  160. 相交链表 3  206. 反转链表 4  234. 回文链表 菜鸟做题第三周，语言是 C++ 1  基础知识 1.1  空指针 使用 nullptr 来判断是否为空指针： “NULL 在 C++ 中就是 0，这是因为在 C++ 中 void* 类型是不允许隐式

    2024年02月19日
    浏览(41)
  • LeetCode热题 100整理

    LeetCode热题 100整理

    35. 搜索插入位置 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2: 输入: nums = [1,3,5,6], target

    2024年02月13日
    浏览(38)

  • Leetcode热题100

    暴力：{i,j}直接返回vectorint 哈希表： map: 红黑树 具有自动排序的功能，是非严格的二叉搜索树。map内部的所有元素都是有序的，使用中序遍历可将键值按照从小到大遍历出来。插入的时间是O(logn),查询时间是O(logn)。可以支持所有类型的键值对 unordered_map: 哈希表（也叫散列表

    2024年02月14日
    浏览(52)
  • python算法与数据结构---单调栈与实践

    python算法与数据结构---单调栈与实践

    单调栈是一个栈，里面的元素的大小按照它们所在栈的位置，满足一定的单调性； 性质： 单调递减栈能找到左边第一个比当前元素大的元素 ； 单调递增栈能找到左边第一个比当前元素小的元素 ； 应用场景 一般用于解决第一个大于XXX或者第一个小于XXX这一类的题目 优点：

    2024年01月21日
    浏览(55)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包