7.15每日一题题解

数列下标

• 题目链接：https://ac.nowcoder.com/acm/contest/6290/A

涉及知识点：

• 单调栈

solution：

• 该题题意就是求每个数的右边第一个比他的数的下标
• 如果不存在则为0，否则就输出该点的下标
• 这个题数据范围比较小，可以用暴力解决，但是这里有一种更好的做法
• 通过单调栈来解决此类问题，可以大大的减少我们的时间
• 从 n - 1 到 1开始，对于当前的数，如果此时栈顶的元素比这个数还大的，那么此时的答案就是栈顶的元素的下标
• 然后把这个数入栈，如果没找到那么答案就是0，也把这个数放入栈里面
• 这样能保证我们的时间复杂度为线性的

std:

#include <iostream>
#include <queue>
#include <stack>

using namespace std;

int n;
const int N = 1e4 + 10;

int a[N];
int b[N];

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)cin >> a[i];
    b[n] = 0;
    stack<int>stk;
    stk.push(n);
    for(int i = n - 1;i >= 1;i --)
    {
        int t = 0;
        while(stk.size())
        {
            t  = stk.top();
            if(a[i] < a[t])
            {
                break;            
            }
            else
            {
                stk.pop();
            }
        }
        
        if(stk.size())
        {
            b[i] = t;
        }
        else
        {
            b[i] = 0;
        }
        stk.push(i);
    }
    
    for(int i = 1;i<= n;i ++)
    {
        cout << b[i] << ' ';
    }
    
    return 0;
}