NC157 题解 | #单调栈#

题意分析

给我们一个数组，我们需要找出每个位置左边和右边最近的比这个位置的数字小的数的位置、如果没有。那么就用-1表示。

思路分析

暴力模拟

这里，我们先直接按照题目的意思进行暴力模拟，我们遍历整个数组，对于寻找左边的位置，我们从这个位置的前一个位置进行枚举，找到第一个小于的数字直接退出。右边的同理。
代码如下
- 利用双重循环进行求解，总的时间复杂度为 $O (n^{2})$
- 过程中只用了少数几个变量，空间复杂度为 $O (1)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        int n=nums.size();
        vector<vector<int> > ans(n);
        // 枚举每个数字
        for(int i=0;i<n;i++){
            int key=-1;
            // 找到第一个小于当前这个位置的数字，找到就直接跳出循环
            for(int j=i-1;j>=0;j--){
                if(nums[j]<nums[i]){
                    key=j;
                    break;
                }
            }
            ans[i].push_back(key);
        }
        
        // 枚举每个位置
        for(int i=n-1;i>=0;i--){
            int key=-1;
            // 找到当前这个位置后面第一个小于这个数字的位置，找到就直接跳出
            for(int j=i+1;j<n;j++){
                if(nums[j]<nums[i]){
                    key=j;
                    break;
                }
            }
            ans[i].push_back(key);
        }
        
        return ans;
    }
};

单调栈

首先，我们来大致说一下单调栈是什么？栈就是一个先进后出的数据结构，这个可以理解为在箱子里面放置书籍，然后要拿出的时候肯定是在上面的，也就是后进去的会先拿出来。然后单调栈就是我们在元素出入栈的时候维护一个栈内元素都是呈单调增或者单调减的趋势。
这个是一个裸的单调栈的题目，我们直接遍历每个数字，然后用一个单调栈维护比当前这个数字小的数字，对于遍历到的每个数字，我们需要确保栈顶的元素的数值比当前这个数值更小。所以我们需要对栈执行不断出栈。直到满足条件或者栈为空为止。

alt

代码如下
- 单调栈的栈只需要存储一遍序列里面的元素，所以总的时间复杂度为 $O (n)$
- 利用栈来对序列里面的元素进行遍历和存储，总的空间复杂度为 $O (n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        int n=nums.size();
        vector<vector<int> > ans(n);
        // 定义一个单调栈，里面存储元素的数值大小和元素的位置
        stack<pair<int,int> > st;
        for(int i=0;i<n;i++){
            // 如果栈不为空或者栈顶的元素不小于我们当前这个数字
            while(!st.empty()&&st.top().first>=nums[i]){
                st.pop();
            }
            // 如果栈为空，那么说明之前没有比这个数值小的元素了
            if(st.empty()){
                ans[i].push_back(-1);
            }else{
                ans[i].push_back(st.top().second);
            }
            st.push(make_pair(nums[i],i));
        }
        
        while(!st.empty()){
            st.pop();
        }
        
        for(int i=n-1;i>=0;i--){
            // 如果栈不为空，同时栈顶的元素不小于我们当前这个数值，那么我们就进行一个出栈的操作
            while(!st.empty()&&st.top().first>=nums[i]){
                st.pop();
            }
            // 如果栈为空，那么说明这个位置后面没有比这个数值小的元素了
            if(st.empty()){
                ans[i].push_back(-1);
            }else{
                ans[i].push_back(st.top().second);
            }
            st.push(make_pair(nums[i],i));
        }
        
        return ans;
    }
};