题解 | #单调栈#

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
	  使用单调栈来寻找任一个元素的右边第一个比自己大或者小的元素的位置
     *当前遍历的元素nums[i]大于等于栈顶元素nums[st.top()]的情况,我们直接入栈
	 当前遍历的元素nums[i]小于栈顶元素nums[st.top()]的情况，栈顶元素右边第一个小的元素就是nums[i]
     寻找左边第一个比自己大或者小的元素的位置就是在上一个基础上从右往左遍历
     *
     * @param nums int整型vector
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        vector<vector<int>>result;
        vector<int>path;
        stack<int>MonoRightIncreasingStack;
        stack<int>MonoLeftIncreasingStack;
        vector<int>resultLeft(nums.size(), -1);
        vector<int>resultright(nums.size(), -1);
        MonoRightIncreasingStack.push(0);
        MonoLeftIncreasingStack.push(nums.size() - 1);
        for (int i = 1; i < nums.size(); i++ ) {
            if (nums[i] >= nums[MonoRightIncreasingStack.top()]) {
                MonoRightIncreasingStack.push(i);
            } else {
                while (!MonoRightIncreasingStack.empty()&&nums[i] < nums[MonoRightIncreasingStack.top()]) {
                    int temp = MonoRightIncreasingStack.top();
                    resultright[temp] = i;
                    MonoRightIncreasingStack.pop();
                }
                MonoRightIncreasingStack.push(i);
            }
        }
        for (int i = nums.size() - 2; i >= 0; i-- ) {
            if (nums[i] >= nums[MonoLeftIncreasingStack.top()]) {
                MonoLeftIncreasingStack.push(i);
            } else {
                while (!MonoLeftIncreasingStack.empty()&&nums[i] < nums[MonoLeftIncreasingStack.top()]) {
                    int temp = MonoLeftIncreasingStack.top();
                    resultLeft[temp] = i;
                    MonoLeftIncreasingStack.pop();
                }
                MonoLeftIncreasingStack.push(i);
            }
        }
        for (int i = 0; i < nums.size(); i++ ) {
            path.push_back(resultLeft[i]);
            path.push_back(resultright[i]);
            result.push_back(path);
            path.clear();
        }
        return result;
    }
};