题解 | #单调栈#

NC157 单调栈

题意

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

1. 暴力做法

按照题意，两重循环模拟即可。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int> > res;
        for (int i = 0; i < n; i++) {
            int l = -1, r = -1;
            // 找l的时候正向走，因为肯定是越来越近的，所以只要比Nums[i]小，一定会更新到更近的l值
            for (int j = 0; j < i; j++) 
                if (nums[j] < nums[i]) 
                    l = j;

            // 找r的时候反向，同理
            for (int j = n-1; j > i; j--) {
                if (nums[j] < nums[i])
                    r = j;
            }
            res.push_back(vector<int>{l, r});
        }
        return res;
    }
};

时间复杂度： $O(n^2)$ , 两重循环。
空间复杂度: $O(n)$ 定义了长度为 $n$ 的答案数组 $res$ 。

2. 单调栈

题目既然叫单调栈，那肯定是考察单调栈，这个词乍一看陌生又熟悉，我们先来学习下它是一种怎样的数据结构。

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

对于本题来说，数组的下标是单调的，我们维护一个存储下标单调栈，然后遍历数组，做如下动作：

设当前遍历到 a[i],我们比较a[i]和栈顶下标top对应的元素a[top]
如果a[top] >= a[i]: 说明top不会是第i个数的解，更不会是任何i以后的数的解（因为i又比top距离后面的数近，又比top小），就一直把top弹出来直到栈空或者栈顶元素小于a[i].
如果a[top] < a[i]: 说明第i个数的解就是top，因为我们确保了栈里面的数和下标都是单调递增的，且top之前的数肯定比a[top]远，又小，比top优秀的解也会在步骤2中加入栈，所以top就是答案。
因为i可能对是i右侧的候选解，把i加入栈。

这样得到了每一个i左边离i最近且小于arr[i]的位置，然后清空栈，再从右往左遍历，就得到了第二问的答案。

以样例中求l[i]为例，如图演示算法：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int> > res;

        stack<int> s;
        vector<int> l(n), r(n);
        for (int i = 0; i < n; i++) {
            // 如果栈顶元素比nums[i]大，说明肯定需要被淘汰
            // i左边的解都找到了，如上面分析i和i右侧的都不可能是这些更大的元素
            // 所以一直弹栈，淘汰掉那些不可能成为答案的数字
            while (!s.empty() && nums[s.top()] >= nums[i]) {
                s.pop();
            }

            // 如果弹空了，说明i左边谁都比nums[i]大，就是无解，否则栈顶就是答案
            l[i] = s.empty() ? -1 : s.top();

            // i入栈，因为i有可能成为i右边的答案
            s.push(i);
        }

        // 清空
        while (!s.empty())
            s.pop();

        // 倒过来再算一遍，同样逻辑
        for (int i = n-1; i >= 0; i--) {
            while (!s.empty() && nums[s.top()] >= nums[i]) {
                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;

    }
};

时间复杂度: $O(n)$ , 只遍历了一轮数组，且每个数只能入栈、出栈1次，内层循环视为常数2，所以为 $O(n*2)=O(n)$ 。
空间复杂度： $O(n)$ , 定义了大小为n的栈。