单调栈和单调队列的学习及例题(左右侧最近更大数的距离问题和直方图最大矩形问题）

单调队列和单调栈很相似他们是什么区别呢单调栈用来求左右两侧最近更大/小数的距离实现方法是求最小值最大值的最大区间维护一个递增递减的栈当遇到一个比栈顶小的值的时候开始弹栈弹栈停止的位置到这个值的区间即为此值左边的最大区间同时当一个值被弹掉的时候也就意味着比它更小更大的值来了也可以计算被弹掉的值得右边的最大区间。也可以说单调栈是用来求数组内的某个元素x在这个数组内作为最大(小)元素的最左边界/最右边界。因为求x作为最大元素的最左(右)边界就是求左(右)边最近一个更大数的距离。求x作为最小元素的最左(右)边界就是求左(右)边最近一个更小数的距离。注意这里单调递增是指从栈底到栈顶为递增排列单调递减是指从栈底到栈顶为递减排列。单调栈题目包括LintCode 1852. Final Discounted PriceLintCode 510. Maximal RectangleLintCode 126. Max TreeLintCode 122. Largest Rectangle in Histogram单调队列用来求滑动窗口的最大/小值实现方法是求区间最小最大值就维护一个递增的双端队列队中保存原始序列的标号当即将入队的元素的值比队尾的元素的值小大的时候就不断弹掉队尾直到出现比它更小的值当即将入队的元素队首元素的跨度即将入队元素的序号到队首元素序列的区间大于规定区间时就不断弹掉队首直到跨度小于或等于所规定的区间。如此可保证队首元素为最小最大值但不能保证队尾就是原始序列中的最大最小值并维护区间长度。注意这里单调递增是指从队首到队尾递增单调递减是指从队首到队尾递减。最典型的例题就是滑动窗口求最大/小值。见https://blog.csdn.net/roufoo/article/details/78443281注意这个滑动窗口求最大/小值和在全局数据里面求第k大/小的数是完全不一样的后者要用quick select(限固定数据) 或堆(real stream或固定数据)来实现。单调队列也用来求解固定查询区间尾部的RMQ问题。RMQ(x,y)就是询问数组[x,y]区间内部的最小值。如果y固定那么可以用单调队列来求解。注意这里我们不需要从队首pop元素因为没有滑动窗口的限制。单调队列也可以用来求区间内递增序列包含的元素个数。典型例题有LintCode 76: (Longest increasing subsequence)见链接https://blog.csdn.net/roufoo/article/details/102882472补充一些个人总结:单调队列可以从队首和队尾pop值而单调栈只能从栈顶pop值。从这个意义来看单调队列并不是严格意义的队列(不能用queue而必须用deque)而单调栈却是严格意义的栈(可以用stack当然也可以用deque)。单调队列是从队尾push值单调栈是从栈顶push值。从这点来看单调队列的队尾跟单调栈的栈顶是一样的。单调队列通常还有区间长度限制 而单调栈不一定有区间长度限制我看到的题目好像都没有。所以单调栈其实更简单因为不需要实时考虑区间溢出。单调队列求区间最大值用递减队列求区间最小值用递增队列。单调栈求左(或右)侧比当前值大的边界用递减队列(即从栈底到栈顶递减)求左(或右)比当前值小的边界用递增队列。为啥求比当前值大的边界是递减队列呢因为这样才能保证栈顶比新元素小的时候栈顶的下一个元素(和下下一个元素…都比栈顶大)能够挨个和新元素比较。单调栈不一定要用stack用vector也可以。因为vector也有pop_back()函数。栈底用vector[0]即可。单调栈例题例题1左右侧最近更大数的距离问题。 给一个数组返回一个大小相同的数组。返回的数组的第i个位置的值应当是对于原数组中的第i个元素至少往右走多少步才能遇到一个比自己大的元素如果之后没有比自己大的元素或者已经是最后一个元素则在返回数组的对应位置放上-1。简单的例子input: 5,3,1,2,4return: -1 3 1 1 -1此题用暴力法复杂度是O(n^2)。用单调栈的话复杂度是O(n)。这里单调栈里面从栈底到栈顶为递减排列。具体执行顺序:5(对应的序号)入栈。因为3比5小3(对应的序号)入栈。因为1比3小1(对应的序号)入栈。因为2比1大1对应的距离就是2的序号-1的序号1记录在1对应的output数组中。然后1出栈3成为栈顶。因为2比3小所以3不出栈2入栈。因为4比2大2对应的距离就是4的序号-2的序号1记录在2对应的output数组中然后2出栈3成为栈顶。然后4还是比3大3对应的距离就是4的序号-3的序号3记录在3对应的output数组中然后3出栈。因为4没有5大所以5不出站。4入栈。程序跑完了5和4在栈中它们对应的output数组的元素还是-1。vectorint NextLarger(vectorint data) { vectorint output(data.size(), -1); //首先都初始化为-1 stackint monoStack; for (int i0; idata.size(); i) { while(!monoStack.empty() data[monoStack.top()]data[i]) { output[monoStack.top()] i-monoStack.top(); monoStack.pop(); } monoStack.push(i); } return output; }在上面的代码中data[monoStack.top()] data[i] 保证一旦新元素比栈顶大说明栈顶元素刚刚找到右侧比它大的数此时对应的output位置马上就要更新。同时该栈顶元素也完成了任务不能恋栈了要马上pop出来让下面的元素跟这个新元素比试比试。如此反复直到while循环里面条件不成立说明栈已空或新元素已经小于栈顶元素了 。因为所有元素最多出栈入栈一次相当于n个操作平摊在for循环中所以复杂度还是O(n)。详见算法中的amortized analysis。另外稍微回顾一下C的内容。NextLarger()返回的是vector这里返回的时候会调用拷贝构造函数所以虽然output是局部变量但不会出错因为返回的是局部变量的拷贝。这里返回值不可以加引用vector 会导致直接返回局部变量但是函数结束时局部变量已经被析构了。这题稍微修改一下就可以变成求左侧更大数的距离问题(for循环倒过来。例题2 Largest Rectangle in Histogram给定一个直方图假定每个矩形宽度为1求直方图中能够组成的所有矩形中面积最大为多少。简单的例子input: 2,1,5,6,2,3return: 10容易看出面积最大的矩形为高度为5和6的直方图组成的矩形其面积为5 * 2 10。解法1这题实际上等价于:对每个矩形求左右最近的一个比他低的矩形的边界然后左右两侧距离相加(还要-1因为自身算了2遍)×该矩形高度。然后找出所有矩形中该操作的最大值。这样我们前面例题1就可以马上拿来用了。注意这里是要求每个元素左右两侧比它小的元素所以要用单调递增栈(data[monoStack.top()] data[i])。#include iostream #include stack #include vector #include map using namespace std; //rightwards is TRUE, leftwards is FALSE mapbool, vectorint dataMap; void NextSmaller(vectorint data) { vectorint toRight(data.size(), -1); vectorint toLeft(data.size(), -1); dataMap[true] toRight; dataMap[false] toLeft; stackint monoToRightStack; stackint monoToLeftStack; for (int i0; idata.size(); i) { while(!monoToRightStack.empty() data[monoToRightStack.top()]data[i]) { dataMap[true][monoToRightStack.top()] i-monoToRightStack.top(); monoToRightStack.pop(); } monoToRightStack.push(i); } for (int idata.size()-1; i0; --i) { while(!monoToLeftStack.empty() data[monoToLeftStack.top()]data[i]) { dataMap[false][monoToLeftStack.top()] monoToLeftStack.top() - i; monoToLeftStack.pop(); } monoToLeftStack.push(i); } return; } int LargestRec1(vectorint data) { //add two dummy boundaries data.insert(data.begin(), -1); data.push_back(-1); NextSmaller(data); //coutRightwardsendl; //for (int i0; idata.size(); i) { // coutdataMap[true][i] ; //} //coutendl; //coutLeftwardsendl; //for (int i0; idata.size(); i) { // coutdataMap[false][i] ; //} //coutendl; int maxV0; int index0; for (int i0; idata.size(); i) { int tempV heights[i]0 ? data[i]*(dataMap[true][i]dataMap[false][i]-1) : 0; if (maxV tempV) { index i; maxV tempV; } } return maxV; }这里dataMap[true][i]和dataMap[false][i]分别对应元素i往右和往左遇到最近的小于它的元素的距离。注意上面是求左右两侧最近更小数的距离问题所以是data[monoStack.top()]data[i]。该不等式表面一旦新元素比栈顶元素小说明栈顶元素已经找到一侧最近更小数了此时要马上记录下栈顶元素在output数组中对应的距离并pop栈顶数组如此反复直到栈空或新元素比栈顶元素大。注意这题要特别注意的是边界条件即左右边界特别大的情况。比如说input是 200,1,5,6,2,3 或 2,1,5,6,2,300则output应该分别是200, 300。所以在LargestRec1()中特地在data[]的左右两侧加入两个dummy -1确保左右两侧会被考虑到。另外回顾一下C的内容。上面的例子中为了练习stl用了mapbool, vector , bool true 为往右侧false为往左侧。还用了2个栈分别对应往左侧和往右侧的单调栈。注意map的初始化:vectorint toRight(data.size(), -1); dataMap[true] toRight;这里dataMap[true] toRight是将toRight数组拷贝到dataMap[true]。所以dataMap[true]后来变了toRight还是没动。解法2:解法1向左向右各扫一遍其实只需要扫一遍就可以了。int LargestRec2(vectorint data) { stackint monoStack; //单调递增栈 int maxV 0; //add two dummy boundaries data.insert(data.begin(), -1); data.push_back(-1); for (int i0; idata.size(); i) { while(!monoStack.empty() data[monoStack.top()]data[i]) { int oldTop monoStack.top(); monoStack.pop(); maxV max(maxV, data[oldTop]*(i-monoStack.top()-1)); } monoStack.push(i); } return maxV; } int main() { vectorint data {2,7,5,6,2,3}; coutLargestRec2(data)endl; return 0; }注意解法2的data[oldTop]*(i-monoStack.top()-1)是不是和解法1的data[i]*(dataMap[true][i]dataMap[false][i]-1)很相似? 这里实际上i-oldTop就是oldTop到右边比它小的最近一个元素的距离oldTop-monoStack.top()就是oldTop到左边比它小的最近一个元素的距离。两者相加要减一因为oldTop本身算了2次。以input为[2,7,5,6,2,3]为例解法2步骤为0) maxV 0。2(对应序号)入栈。2比7小7(对应序号)入栈。5比7小记下7的数值7出栈。7*(2-0-1)7。 这里2和0分别是5和第1个2对应的序号也就是7右侧和左侧最近的更小数的序号。maxV7。注意为简便起见这里的序号没有考虑dummy边界。6比5大6入栈2比6小。记下6的数值6出栈。6*(4-2-1)6。这里4和2分别是第2个2和5对应的序号也就是6右侧和左侧最近的更小数的序号。maxV7。while循环继续2比5小记下5的数值5出栈5*(4-0-1)15。这里4和0分别是第2个2和第一个2对应的序号也就是5右侧和左侧最近的更小数的序号。maxV15。while循环继续(第1个)2不大于(第2个)2所以第2个2入栈。2比3小。3入栈。这里实际上还要考虑左右两边边界的问题。在此两边边界对应的maxV都小于15所以对结果无影响。再总结一下为啥要用单调递增栈呢因为这样可以保证栈内每个元素的下面一个元素(往栈bottom方向)就是该元素左侧最近的更小数当栈顶比新元素大时新元素就是栈顶元素右侧最近的更小数。这样栈顶元素的左右两侧最近的更小数都同时确定了。所以解法2和解法1是等价的但更巧妙。