Monotic-stack: 单调栈的应用

0XFF-96 commented 4 years ago

单调栈调应用

1、https://blog.csdn.net/zuzhiang/article/details/78134247 2、https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/dan-tiao-zhan 3、https://medium.com/algorithms-and-leetcode/monotonic-queue-explained-with-leetcode-problems-7db7c530c1d6 4、https://stackoverflow.com/questions/55780200/intuition-behind-using-a-monotonic-stack

单调栈 leetcode 题目

[ ] 1019_next_greater_value
[ ] next greater element
[ ] 每日温度， https://www.youtube.com/watch?v=d4FvlTzzWjQ 【done】 https://leetcode.com/problems/daily-temperatures/
[ ] https://leetcode.com/problems/online-stock-span/
[ ] next-greater-element 3 : https://leetcode.com/problems/next-greater-element-iii/

https://leetcode.com/problems/next-greater-element-ii/solution/

视频

1、https://www.bilibili.com/video/BV1q7411j7DS?from=search&seid=9613133216781283773 【已看】 2、https://www.bilibili.com/video/BV1q7411j7DS?from=search&seid=9613133216781283773 【单调栈和单调队列】 3、算法体 tapping water : https://www.bilibili.com/video/BV1Et411j7fd?from=search&seid=9613133216781283773
4、online stack span : https://www.youtube.com/watch?v=RGRC46zHB98

概念

什么是单调栈

单调栈，顾名思义，是栈内元素保持一定单调性（单调递增或单调递减）的栈。这里的单调递增或递减是指的从栈顶到栈底单调递增或递减。既然是栈，就满足后进先出的特点。与之相对应的是单调队列。

核心伪代码


for(i=0;i<=n;i++)
{
    if(栈为空或入栈元素大于等于栈顶元素) 入栈;
    else 
    {
        while(栈非空并且栈顶元素大于等于入栈元素)
        {
            栈顶元素出栈;
            更新结果; 
        } 
        将最后一次出栈的栈顶元素（即当前元素可以拓展到的位置）入栈; 
        更新最后一次出栈的栈顶元素其对应的值; 
    }

核心描述

有一组数10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。单调递减的栈反之

应用

最基础的应用就是给定一组数，针对每个数，寻找它和它右边第一个比它大的数之间有多少个数
给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列的长度最大。
给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列所有元素和最大。

0XFF-96 commented 4 years ago

1、https://leetcode.com/problems/next-greater-node-in-linked-list/discuss/402605/Golang-Solution-536-ms-faster-than-96.81-8.4-MB-less-than-100.00 2、1019. Next Greater Node In Linked List 【怎么进行优化】？【min stack 的方法？】

题目特点： Monototic Stack ? – 保证每个元素只会进栈和退栈一次 – 什么时候 pop 和什么时候 push ?

– 活跃，刚看完了，会更加准确判断用户是否在线。不过现在的 last_login_time 其实基本等于低频率的 last_active_time, 因为用户每次调用 api 接口，都会尝试更新 session 的 last_login_time 视频：花花酱 LeetCode 1019. Next Greater Node In Linked List - 刷题找工作 EP246 实现 idea 之前的区别？ 1、第一个比你大的元素。 2、BST, 比你大而且是最小的一个元素。

【youtube 会员才能够 download video ..】好吧

1、这篇文章不错， https://medium.com/algorithms-and-leetcode/monotonic-queue-explained-with-leetcode-problems-7db7c530c1d6 2、https://medium.com/algorithms-and-leetcode 这个系列也不错嘛

0XFF-96 commented 4 years ago