比大小

[编程题]比大小

热度指数：2798 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个整数数组，返回一个数组。该返回数组中第i个数字为，原数组中第i个位置的数字至少往右走多少步才能遇到比它大的数字。如果遇不到或者已经处于最右的位置，则置为-1。

输入描述:

输入为多行，第一行为一个整数N，1≤N≤10⁶

接下来一共有N行，每一行为一个整数M，0≤M≤2³²-1

输出描述:

输出 N 行，每行一个数字表示转换之后的数组

示例1

输入

输出

算法知识视频讲解

Python

小橙子&

本题其实看到数据的大小就知道暴力会超时，特意做了下暴力，然后就是只能AC0.6，随便优化下，只能到了0.8，最后只有大幅度优化，才能AC

N = int(input().strip())
data = []
for i in range(N):
    data.append(int(input().strip()))
dp = [-1] * N
for i in range(N-1,-1,-1):
    cur = data[i]
    j = i + 1
    while j < N:
        if i == N - 1:
            break
        if dp[j] == -1 and cur >= data[j]:
            break
        if data[j] > cur:
            dp[i] = j - i 
            break
        j = j + dp[j]
for i in dp:
    print(i)

发表于 2020-08-21 22:17:19 回复(1)