数据结构：单调栈

1.单调栈

? ? ?单调栈是一种数据结构，其中存放的数据应该是有序的，所以单调栈也有单调递减栈和单调递增栈

单调递增栈：栈顶到栈底的元素大小是从小到大
单调递减栈：栈顶到栈底的元素大小是从大到小

? ? ?单调栈主要就是用来求一个给定序列中每个数左边离它最近的比它大或小的数。如果找的是比它小的数，就是构造一个单调递减栈；如果找的是比它大的数，那构造的就是一个单调递增栈。

2.单调栈模拟

? ? ? 假如我们现在有一个序列10，2，8，5，13，我们要找每个数离它最近的比它大的数，我们要构造一个单调递增的栈，则如果栈为空或者入栈的元素大小小于栈顶值，就入栈，否则入栈会破坏栈的单调性，这时候比入栈元素小的元素全部出栈。

? ? ? 10入栈时，栈为空，直接入栈，栈有一个元素10；

? ? ? 2入栈时，栈顶元素10比2大，则入栈，栈内元素为10和2；

? ? ? 8入栈时，栈顶元素2比8小，则栈顶元素出栈，此时栈顶元素为10，比8大，8可以入栈，栈内元素为10和8；

? ? ?5入栈时，栈顶8比5大，可以入栈，栈内元素为10，8，5；

? ? ?13入栈时，栈顶元素5比13小，出栈；8比13小，出栈；10比13小，出栈，最后栈为空，13入栈，栈内只有12。

? ? ? 单调递减栈的原理和递增类似

代码：

C:

//构造单调递增栈
int top=0；
for(int i=0;i<n;i++)
{
   if(top==0||stk[top]>=i}
   {
     stk[++top]=i;//当前元素入栈
   }
   else
   {
      while(top&&stk[top]<i)
      {
        top--;//出栈
      }
      stk[++top]=i;//当前元素入栈
   }
}

//构造单调递减栈
int top=0；
for(int i=0;i<n;i++)
{
   if(top==0||stk[top]<=i}
   {
     stk[++top]=i;//当前元素入栈
   }
   else
   {
      while(top&&stk[top]>i)
      {
        top--;//出栈
      }
      stk[++top]=i;//当前元素入栈
   }
}

?C++:

//构造单调递增栈
stack<int>stk;
for(int i=0;i<n;i++)
{
  while(!stk.empty()&&stk.top()<i)
  {
    stk.pop()
  }
   stk.push(i);
}

//构造单调递减栈
stack<int>stk;
for(int i=0;i<n;i++)
{
  while(!stk.empty()&&stk.top()>i)
  {
    stk.pop()
  }
   stk.push(i);
}

?3.单调栈应用(C++)

? ? ?其实我们可以看到这也是类似最近匹配的问题，栈最擅长这种问题了

3.1 每日温度

vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> res(temperatures.size(), 0);
        stack<int> stk;
        for (int i = 0; i < temperatures.size(); ++i) {
            while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) {
                res[stk.top()] = i - stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return res;
    }

? ? ? 给定一个温度序列，让你求每个温度离它最近的比它高的温度是之后第几天，显然符合单调递增栈的特征，我们定义一个栈stk来存储每个温度对应的下标和存储结果的vector数组res，从头开始遍历，如果栈为空或者栈顶下标对应的温度大于当前温度值，则当前温度对应的下标入栈；如果不为空且栈顶下标对应的温度小于当前温度值，说明我们找到了这个温度离它最近的比它高的温度值，那我们就把两个温度对应天数的差值放入res数组中，即res[stk.top()]=i-stk.top()，然后再让栈顶元素出栈，把这个温度对应的下标入栈即可，最后返回结果数组res。

3.2 接雨水

int trap(vector<int>& height) {
      int ans=0;
      stack<int>st;
      for(int i=0;i<height.size();i++)
      {
          while(!st.empty()&&height[st.top()]<height[i])
          {
              int cur=st.top();
              st.pop();
              if(st.empty())break;
              int l=st.top();
              int r=i;
              int h=min(height[l],height[r])-height[cur];
              ans+=(r-l-1)*h;
          }
          st.push(i);
      }
      return ans;
    }

? ? ? ?这是一个单调递减栈，当我们找到一根比前面高的柱子时，就可以计算接到的雨水了。更低的柱子我们就入栈，当出现高于栈顶的柱子时，我们就可以计算已经接到的雨水，然后出栈把当前当前的柱子入栈。

? ? ? ? 需要注意的是，雨水的右边r是当前的索引i，底部是栈顶st.top()，因为遇到了更高的柱子，所以雨水的左边即将出栈，使用cur来记录它，l就是新的栈顶，这样雨水的区域就确定了，高度就是左右两边更低的一边减去底部，宽度就是左右中间。