题目的主要信息：

• 给定一个长度为 n 的可能含有重复值的数组 arr ，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置
• 结果返回一个二维数组，表示所有位置相应的信息，如果找不到位置，则相应地方为-1
• 下标0开始
• 进阶要求：空间复杂度 $O(n)O(n)$ ，时间复杂度 $O(n)O(n)$

方法一：暴力解法

具体做法：

遍历数组，对于数组每个元素arr[i]，分别从左边和右边开始向左和向右遍历，查找到第一个小于arr[i]的元素记录位置即可，如果没找到记录-1.

class Solution {
public:
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        vector<vector<int> > res;
        for(int i = 0; i < nums.size(); i++){
            vector<int> temp; //记录第i个答案的临时数组
            int j = i - 1; 
            while(j >= 0 && nums[j] >= nums[i]) //向左遍历找到第一个小于arr[i]的元素
                j--;
            temp.push_back(j); //这里j直接可以为-1
            j = i + 1;
            while(j < nums.size() && nums[j] >= nums[i]) //向右遍历找到第一个小于arr[i]的元素
                j++;
            temp.push_back(j == nums.size() ? -1 : j); //需要判断j为n时加入-1
            res.push_back(temp);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，外层需要遍历整个数组，内层最坏情况遍历两次数组，一共是$O(n^2)O(n^2)$
• 空间复杂度：$O(1)O(1)$，无额外空间，res属于返回必要空间，temp属于常数空间

方法二：单调栈

具体做法：

可以使用两次单调栈来解决这个问题。

第一次单调栈，记录从左往右依次递增的元素，找的也是每个元素右边第一个比它小的元素。我们每次遍历到一个元素，都要将栈中比它的大的元素弹出，而这些被弹出的元素它的右边第一个比它小的数字就是这个要加入栈中的元素，然后将其加入栈中，保证栈中从栈底到栈顶都是递增序的，后续如果遇到一个比它还小的才有机会被弹出，而那也一定是其右边第一个比它小的。如果栈中元素一直无法弹出，则它右边没有更小的元素了， 所以答案全部初始化为-1，只修改可以弹出的元素的位置。

第二次单调栈，录从右往左依次递增的元素，找的也是每个元素左边第一个比它小的元素，整体类似从左往右，不再赘述。

class Solution {
public:
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int> > res(n, vector<int>(2, -1));
        stack<int> s;
        for(int i = 0; i < n; i++){ //查找每个元素右边第一个比它小的数的位置
            if(s.empty()){
                s.push(i);
                continue;
            }
            while(!s.empty() && nums[s.top()] > nums[i]){ //将栈弹空直到本个元素进入栈中
                res[s.top()][1] = i; //栈中比它大的元素的右边第一个小的位置就是i
                s.pop();
            }
            s.push(i);
        }
        stack<int> temp;
        swap(s, temp); //清空栈
        for(int i = n - 1; i >= 0; i--){ //查找每个元素左边第一个比它小的数的位置
            if(s.empty()){   //如果栈为空，加入本个元素
                s.push(i);
                continue;
            }
            while(!s.empty() && nums[s.top()] > nums[i]){ //将栈弹空直到本个元素进入栈中
                res[s.top()][0] = i; //栈中比它大的元素的左边第一个小的位置就是i
                s.pop();
            }
            s.push(i);
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，单独遍历两次数组，栈中元素弹出最多每个元素一次，因此整体复杂度还是$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，res属于返回必要空间，但是单调栈最坏情况下深度为$nn$