下一个更大的数(二)

C++ 解法, 执行用时: 40ms, 内存消耗: 4360KB, 提交时间: 2022-05-21

int stk[100005], top;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> nextBigger(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        for (int i = 2 * n - 1; i >= 0; --i) {
            while (top && nums[i % n] >= stk[top]) --top;
            if (i < n) {
                if (top) ans[i] = stk[top];
                else ans[i] = -1;
            }
            stk[++top] = nums[i % n];
        }
        return ans;
    }
};

C 解法, 执行用时: 40ms, 内存消耗: 5108KB, 提交时间: 2022-05-28

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
struct info
{
    int dat;
    int index;
};

int* nextBigger(int* nums, int numsLen, int* returnSize ) {
    // write code here
    struct info stackDat[numsLen];
    int  stackTop = 0;
    int *returnNums = (int *)malloc(sizeof(int) *numsLen);
    *returnSize = numsLen;
    for(int i = 0 ; i < numsLen; i++)
    {
        //单调 递减栈
        while(stackTop && stackDat[stackTop-1].dat < nums[i])
        {
            returnNums[ stackDat[stackTop - 1].index ] = nums[i];
            stackTop--;
        }
        stackDat[stackTop].dat      =  nums[i];
        stackDat[stackTop].index    =  i;
        stackTop++;
    }

    for(int i = 0 ; i < numsLen; i++)
    {
        while(stackTop && stackDat[stackTop-1].dat < nums[i])
        {
            returnNums[ stackDat[stackTop - 1].index ] = nums[i];
            stackTop--;
        }
    }

    while(stackTop)
    {
        returnNums[ stackDat[stackTop - 1].index ] = -1;
        stackTop--;
    }
    return returnNums;

}

C++ 解法, 执行用时: 40ms, 内存消耗: 5356KB, 提交时间: 2022-04-18

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    struct node
    {
        int val,idx;
        node(int val = 0,int idx = 0):val(val),idx(idx){};
    };
    stack<node> st;
    vector<int> ans;
    vector<int> nextBigger(vector<int>& nums) {
        // write code here
        int len = nums.size();
        if(len == 1) return {-1};
        ans = vector<int>(len);
        st.push(node(nums[0],0));
        for(int i = 1;i<len;++i)
        {
            while(!st.empty()&&nums[i]>st.top().val)
            {
                node& tmp = st.top();
                st.pop();
                ans[tmp.idx] = nums[i];
            }
            st.push(node(nums[i],i));
        }
        if(!st.empty())
        {
            int idx = st.top().idx;
            for(int i = 0;i<len;++i)
            {
                if(i>=idx||st.empty()) break;
                while(!st.empty()&&nums[i]>st.top().val)
                {
                    node& tmp = st.top();
                    st.pop();
                    ans[tmp.idx] = nums[i];
                    idx = st.top().idx;
                }
            }
            while(!st.empty())
            {
                ans[st.top().idx] = -1;
                st.pop();
            }
        }
        return ans;
    }
};

C++ 解法, 执行用时: 41ms, 内存消耗: 4328KB, 提交时间: 2022-07-03

class Solution {
  public:
    int a[100005], d;
    vector<int> nextBigger(vector<int>& nums) {
        int h = nums.size();
        vector<int> z(h);

        for (int i = 2 * h - 1; i >= 0; --i) {
            while (d && nums[i % h] >= a[d]) --d;
            if (i < h) {
                if (d) z[i] = a[d];
                else z[i] = -1;
            }
            a[++d] = nums[i % h];
        }
        return z;
    }
};

C++ 解法, 执行用时: 43ms, 内存消耗: 4580KB, 提交时间: 2022-07-05

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> nextBigger(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n, -1);
        stack<int> s{};
        for (int i = 0; i < 2 * n; i++) {
            while(!s.empty() && nums[i % n] > nums[s.top() % n]) {
                res[s.top() % n] = nums[i % n];
                s.pop();
            }
            s.push(i);
        }
       
        return res;
    }
};

详情