NC157 单调栈（栈）

描述

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

请设计算法，返回一个二维数组，表示所有位置相应的信息。位置信息包括：两个数字 l 和 r，如果不存在，则值为 -1，下标从 0 开始。

输入：[3,4,1,5,6,2,7]
返回值：[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]
进阶：空间复杂度 O(n) ，时间复杂度 O(n)

解题思路

方法一：
单调栈就是栈内元素有单调性的栈。对比普通栈，单调栈的入栈略有不同：单调栈在入栈的时候，需要先判断栈顶的元素，在加入后是否会破坏单调性，如果不会，直接入栈，否则一直弹出直到满足单调性。

class Solution {
public:

    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        stack<int> s;
        int n=nums.size();
        vector<vector<int> > res;
        vector<int> l(n),r(n);
        for(int i=0;i<n;i++){
            while(!s.empty() && nums[i]<=nums[s.top()]){//说明左边没有值比它小
                s.pop();
            }
            l[i]=s.empty()?-1:s.top();//左边最近比他小的值的索引
            s.push(i);
        }
        while(!s.empty()) s.pop();
        for(int i=n-1;i>=0;i--){
            while(!s.empty() && nums[i]<=nums[s.top()]){
                s.pop();
            }
            r[i]=s.empty()?-1:s.top();
            s.push(i);
        }
        for(int i=0;i<n;i++){
            res.push_back(vector<int>{l[i],r[i]});
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

方法二：暴力求解

class Solution {
public:

    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        vector<vector<int> > res;
        int n=nums.size();
        for(int i=0;i<n;i++){
            int l=-1,r=-1;
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i])
                    l=j;
            }
            for(int j=n-1;j>i;j--){
                if(nums[j]<nums[i])
                    r=j;
            }
            res.push_back(vector<int>{l,r});
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间：O(n^2)
空间：O(n)