题解 | #单调栈#

一.题意整合

给定一个长度为n的可能含有重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比 arri小的位置，若不存在即返回值为-1。

二.思路整理

题目的意思很明了使用单调栈，借助单调性处理问题的思想在于即使排除了不可能的选项，保持策略集合的高度有效性和秩序性。

单调栈：单调栈就是使栈内元素单调递增或者单调递减的栈，单调栈也只能在栈顶操作。

while(栈顶元素比入栈元素小且栈不空){
		栈顶元素弹出
}
元素入栈

首先要知道单调栈入栈的的是下标。对于入栈元素直接入栈会破坏单调性，所以需要栈顶元素出栈，后加入当前元素，使得我们当前的元素再加进去不会破坏它的单调性。

让我们模拟一遍单调栈的运行过程，这里的单调栈是单调递增栈。
我们现在有6个数 4,1,7,9,3,6。
我们当前栈内没有元素，将4加入。现在栈内元素应该是4。
当前元素为1，我们发现加入之后不能单调，于是4出栈，加入1。当前栈内元素为2。
接下来是7,9。我们发现加入不会破坏单调性，于是直接加入，栈内元素1,7,9。
遇到3，只能吐出栈内7，9，加入3。
最后加入6。结束。

对于本题来说需要返回左右的最小值，很显然只需要进行两次遍历，第一次遍历啊超出右边的最小值，然后第二次遍历找出最左边最小值。

三.代码实现

class Solution {
public:
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        vector<vector<int>>ans(nums.size(),vector<int>(2,-1));//记录左右的最小值
        stack<int>st;//栈需要维护单调性
        //找到左边的最小值
        for(int i=0;i<nums.size();i++){
            if(!st.size()){
                st.push(i);
                continue;
            }
            while(st.size()&&nums[st.top()]>nums[i]){
                ans[st.top()][1]=i;//左边最小值的记录
                st.pop();
            }
            st.push(i);
        }
        while(st.size()) st.pop();//栈清空
        //反过来找到右边的最小值
        for(int i=nums.size()-1;i>=0;i--){
            if(!st.size()){
                st.push(i);
                continue;
            }
            while(st.size()&&nums[st.top()]>nums[i]){
                ans[st.top()][0]=i;//右边最小值的记录
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }
};