GroupBlog

今天面腾讯, 这道题没想出来

题目要求基本如题, 然后只有一个元素的时候 (最右末尾元素) 对应值为空

当时面试官要求时间复杂度为 O(n), 想了半天也没想出来

提示了使用栈和栈顶指针做, 过了一会时间不够了就问下面的题了, 现在回过头来看一下这道题

这道题我一开始想的是栈中存储对应元素, 但是怎么推都达不到 O(n) 的复杂度, 后来百度了一下, 看到一篇博客, 原来栈中可以存储数组的索引

过程如下:

将数组首元素索引入栈
从第 1 个元素开始遍历数组
如果遍历到的当前数组第 i 个元素 x, 大于栈顶索引对应的元素, 那么这个栈顶索引对应的元素所求的右边第一个比他大的数就是 x, 然后继续处理直到栈为空或者不再大于栈顶索引对应的元素
如果当前遍历到的数组元素小于栈顶索引对应的数组元素, 那么就将该数组元素索引入栈

思路 :
当你遍历到第 k 个元素的时候, 栈中存储的是从 i ~ k - 1 的数组元素下标, 然后挨个将当前元素和栈中存储的对应元素比较, 如果比他们大, 那么他就是每个元素要求的对应值, 直到栈为空或者当前元素不再大于栈顶对应元素了, 那么说明当前这个元素和栈中的元素的右边的最大值都位于当前元素的右边

vector<int> func(vector<int> a, int len)
{
    vector<int> res(len, -1);   //存储结果
    stack<int> sta; //栈
    sta.push(0);    //压入数组第一个元素的下标
    for (int i = 1; i < len; i++)   //遍历数组
    {
        while (!sta.empty() && a[i] > a[(sta.top())])   //栈为空或者当前元素不大于栈顶对应元素
        {
            res[(sta.top())] = a[i];    //如果大于说明当前元素就是他的右边第一个最大值
            sta.pop();  //将栈顶元素出栈
        }
        sta.push(i);    //将当前元素下标入栈
    }
    return res;
}