题目描述

现有一个n天的气温表， 请你预测对于每一天，最迟多少天后可以升温（从现在到气温表中最后大于当前温度的那天）。如果不能升温，则当前输出0。

输入

输入第一行为一个n代表天数。

第二行为n个整数，第i个代表第i天的气温a[i]。

$1 <= n <= 1e6$

$0 < a[i] < 1e6$

输出

输出一行n个数，第i个数代表对于第i天，最迟多少天后可以升温，如果不能升温，输出0。

输入样例

5
1 2 5 3 2

输出样例

4 2 0 0 0

分析

对于数组里面的每一个数，我们需要找到每个数右边最后一个比它大的数。如果是让我们求右边第一个比他大的数时，我们可以利用单调栈，逆序读入每个数，维护栈的单调性即可。由于本题中需要求的是最后一个大于它的元素，需要另辟蹊径。

考虑这样一个性质，将数组元素的值从大到小遍历，其中我们需要存储下这些元素排序前的原始下标。

对于数组中的最大元素，它右边肯定不可能有比他更大的元素，所以该元素的答案肯定是0，对于第二大的元素，如果它在最大元素的右边，即它的右边也不可能有比他更大的元素；如果他在最大元素的左边，显然最大元素的位置即为它的答案。后续遍历的所有元素都只会比之前遍历的元素要小，所以我们只需要用一个变量标记当前最大元素的下标即可。

代码如下:

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int wd,id;
}a[1000005];
int ans[1000005]={0};
bool cmp(const node&b,const node&c)
{
    if(b.wd==c.wd)
        return b.id>c.id;
    return b.wd<c.wd;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&(a[i].wd));
        a[i].id=i;
        ans[i]=0;
    }
    sort(a+1,a+n+1,cmp);
    int maxid=0;
    //for(int i=1;i<=n;i++)
        //printf("%d %d\n",a[i].wd,a[i].id);

    // maxid用来保存当前温度最大的是第几天
    for(int i=n;i>=1;i--)
    {
        // 由于是从后往前遍历，所以当前温度相等时，天数小的要排在后面
        // 这样
        if(a[i].id<maxid)
        {
            cout << "天数"<< a[i].id <<"小于" << maxid << endl;
            cout << "----更新第"<< a[i].id << "天的答案为" << maxid-a[i].id << endl;
            ans[a[i].id]=maxid-a[i].id;
        }
        else
        {
            cout << "天数"<<  a[i].id <<"大于" << maxid << endl;
            cout << "--更新maxid为" << a[i].id << endl;
            maxid=a[i].id;

        }
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

测试输出：

天数3大于0
--更新maxid为3
天数4大于3
--更新maxid为4
天数2小于4
----更新第2天的答案为2
天数5大于4
--更新maxid为5
天数1小于5
----更新第1天的答案为4
4 2 0 0 0

思路二： 二分

先求出一个数组mx，mx[i]代表a[i..n]的最大值。然后对第i天，二分查找 [i+1, n] 内大于a[i]的最后一个位置，复杂度O(nlogn)

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;
int a[N], maxn[N];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i<=n; i++) {
        scanf("%d", a+i);
    }

    int max = -1;
    for (int i = n; i>0; i--) {
        if (a[i]>max) maxn[i] = a[i], max = a[i];
        else maxn[i] = max;

    }

    for (int i = 1; i<=n; i++) {
        int l = i+1, r = n;
        while (l < r) {
            int mid = (l+r+1)/2;
            if (maxn[mid] > a[i]) l = mid;
            else r = mid-1;
        }
        if (maxn[r] <= a[i]) cout << 0 << ' ';
        else cout << r-i<< ' ';
    }
    return 0;
}