单调栈的作用是:用 单调栈 - 图1的时间得知所有位置两边第一个比他大(或小)的数的位置。

递增（减）栈

应用场景：
针对某个数，寻找它和它【左/右】两边第一个比他【大/小】的数，以及相距多少距离。 1.> 接雨水 针对某个洼地，当前能接的雨水等于左右两侧【最大高度】的最小值-当前洼地的高度。（> 单调栈 - 图2）
对于某个洼地来说，其能盛水的量由【左右边界确定】，对于洼地> 单调栈 - 图3> ,显然1的左边届由0界定，将其加入栈中，待确定其右边界，当有 单调栈 - 图4显然1的右边界由2界定，弹出1，其为最低高度，并得到当前栈顶0故0-1-2之间可以存水【单调栈 - 图5】 【stack.top() ↓> 】

2.柱形图中最大的矩形 针对某个柱子，其能形成的最大矩形由其左右两侧【最近的小于其高度】的柱子决定（> 单调栈 - 图6） 1.针对某个柱子p，在其> （> 从前向后遍历> ）> 之前> 有> 单调栈 - 图7> ,则其必然不被单调栈 - 图8所界定左边界（因为单调栈 - 图9比较小，离p更近，单调栈 - 图10）。当遍历到柱子p时，若> 栈顶元素>p（说明p之后的柱子由p来界定左边界，栈中比p高的柱子都没机会了，此时也说明当前st.top元素的右边界为p（离的最近且小））,应弹出> ，直到> 栈顶元素<p> ，则该栈顶元素为柱子p的左边界。> 【stack.top()＞cur,弹出，故使用递增栈> ↑> 】 2.同理右边界 3.算出每个柱子所能得到的最大矩形即可 3.牛向右看能看多少只其他牛。 针对某个牛，其能看到的牛的个数由其右侧【最近的高于其高度的牛】所决定(> 单调栈 - 图11> ) 1.针对某个牛p，假设> （从后向前遍历）> 其后> 有> 单调栈 - 图12> ，其右边界必不为单调栈 - 图13所界定（因为单调栈 - 图14且单调栈 - 图15又高）。当遍历到牛p时，若栈顶元素p,则该栈顶元素为p的右边界。> 【> stack.top()<cur,确定右边界，弹出，故使用递减栈↓】**

1.定义

  • 从栈底元素到栈顶元素呈单调递增或单调递减，栈内序列满足单调性的栈；

    2.原理

  • 当新元素在单调性上优于栈顶时（单增栈新元素比栈顶大，单减栈新元素比栈顶小），压栈，栈深+1；

  • 当新元素在单调性与栈顶相同（新元素于栈顶相同）或劣于栈顶时（单增栈新元素比栈顶小，单减栈新元素比栈顶大），弹栈，栈深-1；

    3.应用

    1.求最长的单调上升、递减区间

    eg.Loongint的花篮

如果对于区间Si,Sj中任意的花篮都比Si高且比Sj低，那么这个区间称为一个美学区间。 如果根本不存在美学区间，输出-1。 如果存在美学区间，那么如果任意区间的长度都小于等于k，那么输出最大的长度，否则输出最大长度比k大多少（MaxLength-k）。

2.针对每个数，寻找它和它左 / 右边第一个比它大 / 小的数的值，以及相距多少个数

有一群牛站成一排，每头牛都是面朝右的，每头牛可以看到他右边身高比他小的牛。给出每头牛的身高，要求每头牛能看到的牛的总数。

解析：

对于第i头牛，假设其后续能观测到的牛的标号分别为[i+1,i+2,.....,s],且height[i+1,....,s]<height[i]，则其观测到牛的总数为s-i+2;
归纳一下该问题解法：

  1. 枚举某一头牛i，其高度为height[i]
  2. 随后向后扩展，使得右侧所有牛的高度均＜height[i]。换句话说，即找到右侧最近的高度>height[i]的牛的位置；

    对于两头牛单调栈 - 图16单调栈 - 图17，则任何在单调栈 - 图18之前的牛，单调栈 - 图19一定不会是右侧最近的高度>height[i]的牛的位置；

由于寻找右侧最近较高的位置，故采取递增栈，存取数据为【当前牛所能看到的牛的数量】
对于牛j0，若当前栈顶＞牛单调栈 - 图20,则表示当前栈顶即为其右侧最近较高的位置

3.接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水） 单调栈 - 图21

思想:递减栈

  • 设高度列表为[单调栈 - 图22],遍历此列表，设索引值i
    • 单调栈 - 图23,由于左侧柱子高，柱子高度呈一个递减的态势，此时最左侧的柱子界定了雨水的最高高度，意味雨水高度由单调栈 - 图24
    • 单调栈 - 图25,此时右侧的柱子高，意味这雨水高度由单调栈 - 图26界定，并将该柱子高度差值（即雨水量）存入ans;

      算法

  1. 初始化：单调减栈stack
  2. 遍历：记每个节点为单调栈 - 图27
    1. 判断：若栈不空且栈顶元素＜单调栈 - 图28,则单调栈 - 图29。
      1. 取出洼地：得当前stack.top()的值，记为j，并出栈。
      2. 雨水长度：出栈后若栈仍不为空，说明存在左边界，记录为stack.top()，则单调栈 - 图30否则单调栈 - 图31
      3. 雨量高度：单调栈 - 图32
      4. 将当前雨水高度存入ans
    2. 入栈：将柱子位置i入栈
  3. 遍历完成时返回ans

    实现

  1. int trap(vector<int>& height) {
  2.     stack<int> s;
  3.     int n=height.size(),ans=0;
  4.     for(int i=0;i<n;i++){
  5.         while(!s.empty() && height[i]>height[s.top()]){
  6.             int idx=s.top();
  7.             s.pop();
  8.             int dis=s.empty()?0:(i-s.top()-1);
  9.             int bound_height=dis==0?0:(min(height[i],height[s.top()])-height[idx]);
  10.             ans+=dis*bound_height;
  11.         }
  12.         s.push(i);
  13.     }
  14.     return ans;
  15. }

4.多个区间中的最值 / 某个数为最值的最长区间

eg.POJ 2796

给你一段区间，需要你求出（在这段区间之类的最小值*这段区间所有元素之和）的最大值

5.柱状图中最大的矩形：

求直方图中的最大矩阵 For example, Given height = [2,1,5,6,2,3], return 10. 单调栈 - 图33

2.POJ 3494（题1的二维版本）

求仅由0，1组成的矩阵中，全部由1组成的小矩阵的最大面积。

思路

关键在于查找height[i]的左右边界，满足当前height[i]对应的最大面积为(r-l-1)*height[i]；

  • 单调栈前一个元素为左边界
  • 单调栈出栈时，说明其后出现了比栈顶更小的元素，故该元素为栈顶元素的右边界

  • 由上知，采用非严格单调递增栈

    算法

    当栈不为空且Height[current]<Height[st.top()]:

  • 获取top,出栈；

  • 判断当前栈是否为空
    • 非空则r=current,l=st.top()
    • 空则r=current,l=-1
  • 则当前面积为(r-l-1)*height[i]
    1. int largestRectangleArea(vector<int>& heights) {
    2.   stack<int> st;
    3.   int n=heights.size(),ans=0;
    4.   heights.push_back(-1);
    5.   for(int i=0;i<n+1;i++){
    6.       while(!st.empty() && heights[st.top()]>heights[i]){
    7.           int idx=st.top();
    8.           st.pop();
    9.           int l=st.empty()?-1:st.top();
    10.           ans=max(ans,(i-l-1)*heights[idx]);
    11.       }
    12.       st.push(i);
    13.   }
    14.   return ans;
    15. }

6.★★子数组的最小值之和

给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。 由于答案可能很大，因此返回答案模 10^9 + 7。

思路

关键在于寻找A[i]所属的区间，满足A[i]为该区间内的最小值

  • 单调栈的前一个元素为该元素的左边界

  • 单调栈出栈时，说明其后出现了比栈顶更小的元素，该元素为栈顶元素的右边界。

    算法

    当栈不为空且A[current]<=A[st.top()]时：

  • 获取top，并出栈

  • 求取current左侧连续n个大于A[current]
    n=top-st.top
  • 求取右侧连续m个大于A[current]
    m=current-top
  • 求得连续子数组数量为m+n+mn+1=(m+1)*(n+1)
  • ans+=(m+1)*(n+1)
  • current++;

注：为保证所有元素出栈！在原数组最后push一个最小的数！

实现

  1. int sumSubarrayMins(vector<int>& A) {
  2.     stack<int> inc_stack; //单调递增栈, 存储的是数组A的索引
  3.     A.push_back(-1); //保证栈里所有元素都弹出
  4.     int len = A.size();
  5.     // {__n__    A[i]    ___m____ };    如 8, 4, 6, 5, 7, 9, 3, 0 -> 对于A[i] = 5, n = 1 ([6]), m = 2 ([7, 9]) 
  6.     // A[i]左侧有n个连续的大于A[i]的数, 右侧有连续m个大于A[i]的数, 则A[i]作为最小值的数组个数为(m+1)*(n+1)
  7.     // 关键即为找到每个A[i]对应的区间, 满足A[i]为该区间内的最小值
  8.     int ans = 0;
  9.     for(int i = 0; i < len; i++){
  10.         while(!inc_stack.empty() && A[inc_stack.top()] >= A[i]){ // A[i]比栈顶元素小, 说明栈顶元素的区间截止, 该处理栈顶元素
  11.             int index = inc_stack.top(); //取栈顶索引
  12.             inc_stack.pop();
  13.             int pre = index - (inc_stack.empty()? -1 : inc_stack.top()); //对应n+1
  14.             int after = i - index;   //对应m+1
  15.             ans += A[index]*pre*after;   //A[i]作为最小值的次数为(m+1)*(n+1), 即ans加上A[i]*(m+1)*(n+1)
  16.         }
  17.         inc_stack.push(i);