【算法总结】单调栈或队列

单调栈

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

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

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

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

例1

题目描述：

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

Example：

Input

5,3,1,2,4

Output

-1 3 1 1 -1

Solution

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

vector<int> stepToGreater(vector<int> &nums){
    int n = nums.size();
    if (n < 1)
        return{};
    nums.push_back(INT_MIN);
    vector<int> res(n, -1);
    stack<int> 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<int> v{ 5, 3, 1, 2, 4 };
    vector<int> res = stepToGreater(v);
    for (auto n : res){
        cout << n << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}

例2：【LeetCode】084. Largest Rectangle in Histogram

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

单调队列

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

例题：【队列】滑动窗口的最大值，类似的还有求最小值问题。