首页 > 试题广场 >

比大小

[编程题]比大小

热度指数：2759 时间限制：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)

zxcv19

import sys
array = list(map(int,sys.stdin.readlines()))
result, array, cur_max = [-1] * array[0], array[1:], array[len(array)-1] 
for idx, val in enumerate(array[::-1]):
    cur_idx = len(array) - 1 - idx
    if cur_idx < len(array) - 1: 
        if val < array[cur_idx + 1]: 
            result[cur_idx] = 1
            cur_max = max(val, cur_max)
        elif val >= cur_max:
            cur_max = val
        else: 
            jump = result[cur_idx+1]
            idx2 = cur_idx + 1 + jump
            while idx2 < len(array):
                if val < array[idx2]:
                    result[cur_idx] = idx2 - cur_idx 
                    break
                jump = result[idx2]
                idx2 = idx2 + jump
for pos in result:
    print(pos)

发表于 2020-03-29 09:44:50 回复(2)

敛先生

num = int(input())
block, stack, result = [], [], []
for i in range(num):
    block.append(int(input()))
    result.append(-1)

i = 0
while(i<num):
    if (not(len(stack)==0)) and (block[i]>block[stack[-1]]):
        cur = stack.pop()
        result[cur] = i - cur
        
    else:
        stack.append(i)
        i += 1

for i in range(len(result)):
    print(result[i])

发表于 2020-03-25 20:33:47 回复(2)

pein531

称每个元素右边第一个比它大的元素为右大元素，然后利用栈开始搜索🤣

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strNum;
        while((strNum = br.readLine()) != null){
            int n = Integer.parseInt(strNum);
            int[] data = new int[n];
            for(int i = 0; i < n; i++)
                data[i] = Integer.parseInt(br.readLine());
            int[] res = new int[n];
            Arrays.fill(res, -1);
            int i = 0;
            // 栈用于存储待寻找右大元素的下标
            Stack<Integer> stack = new Stack<>();
            // 遍历数组元素，优先寻找栈顶元素的右大元素
            while(i < n){
                if(!stack.isEmpty() && data[i] > data[stack.peek()]){
                    /* 如果栈不为空，且当前元素大于栈顶元素时直接
                    计算当前元素与最近右大元素的距离*/
                    int cur = stack.pop();    // 栈顶元素的右大已经找到，弹出
                    res[cur] = i - cur;
                }else{
                    // 否则将当前元素的下标加入栈
                    stack.push(i);
                    i += 1;
                }
            }
            for(Integer distance: res)
                System.out.println(distance);
        }
    }
}

发表于 2021-01-14 09:27:42 回复(0)

pyxiea

使用单调栈，复杂度O(N)，具体解释以及类题，可以见博客：https://blog.csdn.net/xpy870663266/article/details/104935930

import sys

N=int(input().strip())
nums=[int(input().strip()) for _ in range(N)]
res=[-1]*N
stack=[]

for i in range(N-1,-1,-1):
    while len(stack)>0 and nums[i]>=nums[stack[-1]]:
        stack.pop()
    res[i]=stack[-1]-i if len(stack)>0 else -1
    stack.append(i)
print('\n'.join([str(x) for x in res]))

编辑于 2020-05-10 10:29:06 回复(0)

kkY_

单调栈

https://blog.csdn.net/qq_17550379/article/details/86494645

import sys
n = int(input())
d = []
for line in sys.stdin:
    d.append(int(line))

stack = []
res = [-1] * n 
for i, value in enumerate(d):
    while stack and d[stack[-1]] < value:
        idx = stack.pop()
        res[idx] = i - idx
    stack.append(i)
print(*res, sep = '\n')

发表于 2021-08-25 15:26:33 回复(1)

小鹿斑比

importjava.util.*;
 
publicclassMain {
    publicstaticvoidmain(String[] args) {
        //从后往前维护一个单调递减的栈，栈中保存的是索引，如果栈顶元素小于当前值，就pop栈顶元素
        //当前位置的值为栈顶元素减当前值，如果栈为空，直接设置为1
        Main test = newMain();
        Scanner in = newScanner(System.in);
        intlen = in.nextInt();
        int[] data = newint[len];
        int[] res = newint[len];
        for(inti = 0; i < data.length; i++) {
            intnum = in.nextInt();
            data[i]=num;
        }
        ArrayDeque<Integer> deque = newArrayDeque<>();
        for(inti = data.length-1; i >= 0; i--) {
            while(!deque.isEmpty()&&data[deque.getLast()]<=data[i]){
                deque.pollLast();
            }
            if(deque.isEmpty()){
                res[i]=-1;
            }else{
                res[i]=deque.getLast()-i;
            }
            deque.offer(i);
        }
 
        for(intre : res) {
            System.out.println(re);
        }
    }
}

发表于 2021-02-24 23:07:17 回复(0)

栗子🌰🌰🌰

求问，我的输出结果最后为什么会有个None??

def rightbig(n,a):
    for i in range(n):
        temp=a[i:]
        if a[i]==max(temp):
            print(-1)
        else:
            count=-1
            for j in temp:
                count+=1
                if j>a[i]:
                    print(count)
                    break

if __name__=='__main__':
    a=[]
    n=int(input())
    for i in range(n):
        a.append(int(input()))
    print(rightbig(n,a))

编辑于 2021-02-21 10:37:50 回复(1)

triumphue

import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] d = new int[n];
        for(int i=0; i<n; i++){
            d[i] = in.nextInt();
        }
        int[] ret = help(d);
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<ret.length; i++){
            sb.append(ret[i]).append("\n");
        }
        System.out.print(sb.toString());
    }
     
    private static int[] help(int[] nums){
        int[] ret = new int[nums.length];
        Arrays.fill(ret, -1);
        Stack<Integer> s = new Stack<>();
        for(int i=0; i<nums.length; i++){
            while(!s.isEmpty() && nums[i] > nums[s.peek()]){
                int top = s.pop();
                ret[top] = i - top;
            }
            s.push(i);
        }
        return ret;
    }
}

发表于 2020-07-23 19:34:04 回复(0)

gogogoovo

C++

#include <vector>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

vector<int> solution(vector<int> &input){
    vector<int> res(input.size(), 0);
    int temp = input.size()-1;
    stack<int> store;
    for(int i = temp; i >= 0; i--){
        while(!store.empty() && input[i] >= input[store.top()]){
            store.pop();
        }
        if(store.empty()) res[i] = -1;
        else res[i] = store.top()-i;
        store.push(i);
    }
    return res;
}

int main(void){
    int total;
    cin >> total;
    int number;
    vector<int> input;
    for(int i = 0; i < total; i++){
        cin >> number;
        input.push_back(number);
    }
    vector<int> res = solution(input);
    for(auto cha : res) cout << cha << endl;
    return 0;
}

编辑于 2020-05-23 17:29:05 回复(0)

Java

一只树

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int[] list = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[i]) {
                    list[i] = j - i;
                    break;
                }
                list[i] = -1;
            }
        }
        list[n - 1] = -1;
        for (int i : list) {
            System.out.println(i);
        }
    }
}

发表于 2020-04-15 18:04:55 回复(1)

觅途


N = int(input().strip())
arr = []
for i in range(N):
    arr.append(int(input().strip()))
for j in range(N): 
    k=1
    while k<N-j: 
        if arr[j+k]>arr[j]:
            print(k)
            break
        k+=1
    else:
        print(-1)
还有什么办法优化这个代码嘛？

编辑于 2020-03-12 15:28:03 回复(2)

BugAngel

#include <iostream>
(720)#include <stack>
#include <string>
 
using namespace std;
 
const int MAXN = 1000005;
int num[MAXN];
int des[MAXN];
 
int main()
{
    int n;
    cin>>n;
    stack<int> stack;
 
    for (int i = 0; i<n; i++) {
        cin >> num[i];
        des[i] = -1;
    }
    int index = 0;
    while (index<n) {
        if (!stack.empty() && num[stack.top()]<num[index]) {
            int cur = stack.top();
            stack.pop();
            des[cur] = index - cur;
        }
        else {
            stack.push(index);
            index++;
        }
    }
    for (int i = 0; i<n; i++) {
        cout << des[i] << endl;
    }
    return 0;
}

发表于 2020-03-12 02:58:52 回复(0)