单调栈

　　单调栈，就是一个栈，里面的元素满足一定的单调性。（多见于单调增/单调减）

1）新元素加入栈前，会在栈顶端把破坏栈单调性的元素都删除，直到栈为空或者栈满足单调性才能加入新元素。

2）单调栈是 O(n) 级的时间复杂度，所有元素只会进入栈一次，并且出栈后再也不会进栈。

3）单调栈可以找到元素向左遍历第一个比他小（大）的元素，也就是说在元素进栈前他向左拓展的区间已经确定，在出栈前她能向右拓展的区间也能确定（左区间好理解，仔细体会右区间的确定，若该元素至遍历结束后也未出栈，那么就是说在原数组中，该元素的右方向没有一个元素可以比它大/小，那么该元素的右边界就是原数组的大小（就是没有右边界），否则它的右边界就是令它出栈的元素）。

例1

题目描述：

　　给定一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）

Example：

Input5,3,1,2,4Output-1 3 1 1 -1

Solution

#include 
     
      #include 
      
       #include 
       
        using namespace std;vector
        
          stepToGreater(vector
         
           &nums){    int n = nums.size();    if (n < 1)        return{};    nums.push_back(INT_MIN);    vector
          
            res(n, -1); stack
           
             s; for (int i = 0; i <= n; ){ if (s.empty() || nums[s.top()] >= nums[i]) s.push(i++); else { int cur = s.top(); s.pop(); res[cur] = i - cur; } } nums.pop_back(); return res;}int main(){ vector
            
              v{ 5, 3, 1, 2, 4 }; vector
             
               res = stepToGreater(v); for (auto n : res){ cout << n << " "; } cout << endl; system("pause"); return 0;}
             
            
           
          
         
        
       
      
     

例2：

 

　　通常来讲，单调栈更倾向于一维数组的问题，或者是多维数组可以转化为一维数组的问题。多存储元素坐标而非元素值。问题多见于寻找数组元素左区间或右区间最大最小问题，或者找出元素的两边界问题。

单调队列

　　单调队列其实和单调栈差不多，一个思想：栈或队列中元素满足单调性，当有新元素要入栈或者入队的时候，要和栈顶或者队尾元素进行比较，满足单调的性质则入队或入栈，否则将栈顶或队尾元素删去，直到满足单调性质，然后将新元素入队或入栈。

例题：，类似的还有求最小值问题。