这里是我的blog：有更多算法分享。排版可能也会更好看一点=v= https://endlesslethe.com/monotone-queue-and-stack-tutorial.html
笔者在做leetcode的题(下一个出现的最大数字)时，接触到了单调栈这一种数据结构，经过研究之后，发现单调栈在解决某些问题时出奇的好用，下面是对单调栈的性质和一些典型题目。
在刷 LeetCode 的时候，每次遇到精彩的题解都会感叹数据结构的伟大，通过巧妙地设计,能够非常清晰明了的解决问题。
什么时候用单调栈呢？ 通常是一维数组，要寻找任一个元素的右边第一个比自己大或者左边第一个比自己小的元素的位置，此时我们就要想到可以用单调栈了。 时间复杂度为O(n)。 单调栈的本质 空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素大的元素 优点是只需要遍历一次。 在使用单调栈的时候首先要明确如下几点： 单调栈里存放的元素是什么？ 单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取
最近有几位球友问我，不知道怎么使用单调栈解决实际问题，今天我通过一道leetcode题目，来详细解读如何使用单调栈。
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
单调栈，是指栈内元素从栈底到栈顶单调递增或单调递减的栈。简单来讲，单调栈=单调 + 栈，它同时满足两个特性：单调性、栈。
单调栈 单调栈是解决这样一类问题 给出$n$个数，问每一个数向左第一个比它小的数是谁 如果直接暴力的话，最坏情况下肯定是$O(n^2)$的，但是单调栈可以在$O(n)$的时间内解决这类问题 实现 单调栈，顾明思议嘛，就是维护一个具有单调性的栈，至于是单调递增还是单调递减，这个视题目而定 对于上面那个问题而言，我们需要维护一个单调上升的序列 加入一个元素的时候，若当前元素比栈顶元素小，那么就不断的弹出栈顶元素，直到整个栈满足单调 那么该位置向左第一个比它小的就是栈顶 上面说的太抽象了 比如，我们有一个序
2、去除冗杂状态 如上题，区间中的两个元素a[i],a[j](假设现在再求最大值)
之前遇到一个算法题目，自己只会用时间复杂度 O(N^2) 暴力解法解决，有大佬说用单调栈，可以做到 O(N) 的时间复杂度，当时我的表情是这样的：
这几天群里打卡的几道题都是十分经典的面试题，经典是因为这些题都是一题多解的。在这些高效的解法中，单调栈是一个很有技巧的解法，所以这一次我们来聊聊这个单调栈。
本文主要利用单调栈来解决leetcode上的典型问题，其实它的应用范围倒是不广，主要解决的都是类似于leetcode上下一个更大元素的问题，本文将从这类问题出发，帮助大家掌握单调栈的应用技巧。主要题型如下所示：
在 LeetCode 1475、商品折扣后的最终价格 一题中，我写的代码是从右向左遍历的。
给你一个数组，要求你找到数组中每个元素左边第一个比他大的数和右边第一个比它大的数，举个例子，数组[3,5,2,1,6]，3左边比他大的没有，右边比他大的是5；5左边比它大的没有，右边比他大的是6；2左边比它大的是5，右边比他大的是6；1左边比他大的是2，右边比他大的是6；6左边比他大的没有，右边比它大的没有
根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
在上一篇文章中[2]，我们介绍了单调栈这种特殊的栈结构，单调栈是一种非常适合处理 “下一个更大元素问题” 的数据结构。今天，分享到单调栈的孪生兄弟 —— 单调队列（Monotonic Queue）。类似地，单调队列也是在队列的基础上增加了单调的性质（单调递增或单调递减）。那么单调队列是用来解决什么问题的呢？
单调栈，就是一个栈，不过栈内元素保证单调性。即，栈内元素要么从小到大，要么从大到小。而单调栈维护的就是一个数前/后第一个大于/小于他的数。
今天分享到一种栈的衍生数据结构 —— 单调栈（Monotonic Stack）。栈（Stack）是一种满足后进先出（LIFO）逻辑的数据结构，而单调栈实际上就是在栈的基础上增加单调的性质（单调递增或单调递减）。那么，单调栈是用来解决什么问题的呢？
链接：84. 柱状图中最大的矩形 - 力扣（LeetCode） (leetcode-cn.com)
单调栈的实质是有单调性的栈，包括单调递增栈和单调递减栈。通过栈的入栈和出栈维护一个动态的滑动窗口，然后栈顶元素是该窗口的最大值或最小值，通过一次遍历，就可以计算出所有元素的下一个较大值或较小值。
单调栈是一种特殊的栈，特殊之处在于栈内的元素都保持一个单调性。 假设下图是一个栈内元素的排列情况(单调递增的栈)：
单调栈是在栈基础上进行变化后的数据结构。除了遵循栈的先进后出的存储理念，在存储过程中还需保持栈中数据的有序性。
给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。
对于栈这种数据结构，相信大部分同学都会觉得很简单，它只有一个特性，那就是先进后出。
单调栈是递增的，每个长方形入栈时，都和栈顶的长方形高度对比，如果大于，则入栈。如果小于则按照高度合并长方形，直到比它高度小的元素，然后再进栈。
https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
如果你对这篇文章可感兴趣，可以点击「【访客必读 – 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。
栈有很多用途，也分很多种类，顺序栈、双端栈、单调栈、链栈等。让哥哥带你，深入浅出堆栈系列。坐好上车咯。
今天给大家带来的是一道特别特别特别经典的题目接雨水问题，这个问题是很多算法书上面举例过的题目。虽然是难度题，但是相对来说还是比较容易理解的，代码长度也适中，说了这么多，就一个意思，大家记得打卡这个题目啊，真的是很nice的一道题，下面我们来看一下题目描述。
单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。
单调栈是满足单调性的栈，即在栈的基础上，维持栈内元素的单调性。典型题目如：有找某侧最近一个比其大(小)的值。
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
栈(Stack)是一种操作受限的线性表，只允许一端进，同一端出，因而具有后进先出(LIFO)的特性。
最近几天接触了单调队列，还接触了单调栈，就总结一下。 其实单调队列，和单调栈都是差不多的数据类型，顾名思义就是在栈和队列上加上单调，单调递增或者单调递减。当要入栈或者入队的时候，要和栈头或者队尾进行比较，满足单调的性质则入队入栈，否则将当前元素删去，直到满足单调性质。 那么问题来了，单调队列，和单调栈有什么用了。最普遍的最重要的作用就是起到优化的作用。当然我目前也只知道这个所用。 先看一道例题： 求一个n序列中，所有长度不大于lmaxin，的连续子序列中，序列和最大的是多少
袁厨携袁记菜馆全体工作人员祝大家在新的一年，健健康康，开开心心。发量暴增，钱包超大。
给定一个长度为 n 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 -1。
一 题目： 二 思路： 单调栈 这里注意，如果气温在这之后都不会升高，则将该位置用0来代替。 根据以上的信息，我们可以先创建一个temperatures等长的全零数组，然后初始化一个栈 这里注意由于需要返回相差天数，所以栈中需要保存元素下标来实现天数计算。 下来循环temperatures进行栈的操作，循环过程中，持续判断当前下标温度与栈顶下标温度的大小差别 如果当前下标的温度大于栈顶下标的温度，表示找到了下一个更大的温度，弹出栈顶下标，计算天数差别， 更新res[栈顶下标] = 当前下标 -
单调栈是一种用来解决首递增序列问题的数据结构，其满足从栈顶元素到栈底元素单调的性质。单调栈还可以用来解决求矩形统计图中最大内矩形面积的问题，进一步可以用来求最小矩阵和问题。
今天是LeetCode专题第52篇文章，我们一起来看LeetCode第84题，Largest Rectangle in Histogram（最大矩形面积）。
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
「单调栈」首先是一种基于栈的数据结构，只不过通过栈来维护的是单调递增或单调递减的数据。入栈和出栈都是操作栈顶。对于每一个元素都只有一次入栈和出栈的操作，因此时间复杂度为O(N)。
比如下面这一题在某些付费算法专栏里面提供的事错误的思路和代码，挺坑人的，一不小心就浪费时间了。
首先我们来看题面，说是我们有若干个水坝，水坝的宽都是1，但是水坝的高度参差不齐。某一天我们向水坝围起来的部分灌水，一直到灌满为止，请问水坝中存储了多少单位的水？我们可以参考一下下图：
暴力求解法： class Solution { public: vector<int> dailyTemperatures(vector<int>& T) { vector<int> ret; ret.resize(T.size(),0); cout << ret.size() << endl; for (int i = 0; i < T.size(); i++) {
1. 要找到的是一个元素之后下个较大值,这里的关键词是[下个较大值]是其后第一个大于当前元素的值.如例子中,第二个元素4(list[1])对应的下个较大值应为5,而不是8.
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议
