题意整理：

本题题意很明显。给定一个数组，需要找到数组中每个元素左边和右边的第一个比元素小的数字。

方法一：暴力

核心思想：

根据题意，对每一个元素，都各自往左以及往右遍历数组，直到到达数组边界或者找到第一个比元素小的数字即可。

核心代码：

class Solution {
public:
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        int n = nums.size(),res = 0;
        vector<vector<int>> ans(n, vector<int>(2, -1));//初始化为-1
        for(int i = 0; i < n; ++i) {
            res = nums[i];
            for(int j = i - 1; j >= 0; --j) {
                //寻找左边符合条件的值
                if(res > nums[j]) {
                    ans[i][0] = j;
                    break;
                }
            }
            for(int j = i + 1; j < n; ++j) {
                //寻找右边符合条件的值
                if(res > nums[j]) {
                    ans[i][1] = j;
                    break;
                }
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：,对每个元素查找两次，每次的最坏情况都是遍历一侧的全部数字，故相当于遍历数组两次，即为。
空间复杂度：，除了返回的答案数组，只使用了常数个变量。一般不将返回的答案数组作为空间复杂度的计算

方法二：单调栈

核心思想：

可以考虑使用单调栈得到更快的运行速度。
单调栈是基于栈进行操作，在其基础上额外添加一些属性所得的一种数据结构。对于单调栈，其中的数据具有单调性，既栈中数据符合递增或者递减规律。对于单调栈，在对元素压入时，需要先判断栈顶的元素在压栈元素加入后是否会破坏单调性，如果不会，直接压栈，否则一直弹出栈顶元素直到满足单调性或者栈为空。
下图演示了一个保证单调栈的结构：

这保证了栈中元素，越靠近栈底的元素越小。
本题可以使用单调栈来获取左边和右边的第一个小于指定数字的元素位置。
对于本题来说要想找到每一个 位置左边离位置最近且值比 小的位置，需要构造单调递减栈，而每次对一个元素进行寻找时，只需要不断将栈顶大于当前元素的值弹出，直到找到小于当前值的数或者栈为空即可。在记录后，需要将当前元素压入栈。
下面说明为什么这种算法是正确的：对于一个元素，如果栈顶元素比它大，将它弹出将不会影响后续元素查找，因为该值大于当前值，如果该值能够作为后续元素的答案，也即，那么当前值明显是更好的答案。因为此时满足,故有，所以当前值会压入栈中作为更佳答案，将栈顶元素弹出不会影响答案的正确性。

核心代码：

class Solution {
public:
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans(n, vector<int>(2, -1));//初始化为-1
        stack<int> sk1, sk2;//两个单调栈
        for(int i = 0; i < n; ++i) {
            while(!sk1.empty() && nums[sk1.top()] >= nums[i]) {
                sk1.pop();//将所有不符合条件的栈顶元素弹出
            }
            if(!sk1.empty()) ans[i][0] = sk1.top();//栈顶元素即为答案
            sk1.push(i);//当前元素压入
        }
        //对右侧进行相同操作
        for(int i = n - 1; i >= 0; --i) {
            while(!sk2.empty() && nums[sk2.top()] >= nums[i]) {
                sk2.pop();
            }
            if(!sk2.empty()) ans[i][1] = sk2.top();//栈顶元素即为答案
            sk2.push(i);
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：，对一个单调栈来看，每个元素都最多进出栈一次，所以可以判断时间复杂度为
空间复杂度：，最坏情况下，所有元素都需要进栈，所以空间复杂度为