下一个更大的数(二)

[编程题]下一个更大的数(二)

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

给定一个循环的数组 nums ，即 nums 的第一个元素可以视为是最后一个元素的下一个元素。返回 nums 中每个元素的后面第一个比他大的元素，如果不存在比他大的元素，则返回 -1。

例如，有数组 [2,3,4,1] 则返回 [3,4,-1,2] ，其中第一二个元素后面第一个比他们大的元素均是下一个元素，第三个元素是最大的，所以输出 -1，而最后一个元素的下一个元素认为是数组的第一个元素，因此是 2。

数据范围：数组长度满足 $1 \le n \le 10^5 \$ ，数组中的元素满足 $1 \le val \le 10^9 \$

示例1

输入

[2,3,4,1]

输出

[3,4,-1,2]

说明

其中第一二个元素后面第一个比他们大的元素均是下一个元素，第三个元素是最大的，所以输出 -1，而最后一个元素的下一个元素认为是数组的第一个元素，因此是 2

示例2

输入

[4,3,2,1]

输出

[-1,4,4,4]

算法知识视频讲解

查看答案及解析

Java

17c89

import java.util.*;
import java.util.stream.Collectors;

/**
 * NC354 下一个更大的数(二)
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型ArrayList
     * @return int整型ArrayList
     */
    public ArrayList<Integer> nextBigger (ArrayList<Integer> nums) {
        // return solution1(nums);
        // return solution11(nums);
        // return solution111(nums);
        return solution1111(nums);
        // return solution2(nums);
        // return solution22(nums);
    }

    /**
     * 单调栈: 单调减(从右往左)
     * @param nums
     * @return
     */
    private ArrayList<Integer> solution1(ArrayList<Integer> nums){
        int n = nums.size();
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>(n);

        for(int i=n-1; i>=0; i--){
            while(!stack.isEmpty() && stack.peek()<=nums.get(i)){
                stack.pop();
            }
            list.add(0, stack.isEmpty()?-1:stack.peek());
            stack.push(nums.get(i));
        }

        for(int i=n-1; i>=0; i--){
            while(!stack.isEmpty() && stack.peek()<=nums.get(i)){
                stack.pop();
            }
            list.set(i, stack.isEmpty()?-1:stack.peek());
            stack.push(nums.get(i));
        }

        return list;
    }

    /**
     * 单调栈: 单调减(从右往左)
     * @param nums
     * @return
     */
    private ArrayList<Integer> solution11(ArrayList<Integer> nums){
        int n = nums.size();
        Stack<Integer> stack = new Stack<>();
        int[] results = new int[n];

        for(int i=n-1; i>=0; i--){
            while(!stack.isEmpty() && stack.peek()<=nums.get(i)){
                stack.pop();
            }
            results[i] = stack.isEmpty()?-1:stack.peek();
            stack.push(nums.get(i));
        }

        for(int i=n-1; i>=0; i--){
            while(!stack.isEmpty() && stack.peek()<=nums.get(i)){
                stack.pop();
            }
            results[i] = stack.isEmpty()?-1:stack.peek();
            stack.push(nums.get(i));
        }

        ArrayList<Integer> list = Arrays.stream(results) // 创建IntStream
                .boxed() // 将IntStream转换为Stream<Integer>
                .collect(Collectors.toCollection(ArrayList::new));

        return list;
    }

    /**
     * 单调栈: 单调减(从右往左)
     * @param nums
     * @return
     */
    private ArrayList<Integer> solution111(ArrayList<Integer> nums){
        int n = nums.size();
        Stack<Integer> stack = new Stack<>();
        int[] results = new int[n];

        for(int i=2*n-1; i>=0; i--){
            // 单调栈 单调减(从右往左)
            while(!stack.isEmpty() && stack.peek()<=nums.get(i%n)){
                stack.pop();
            }
            results[i%n] = stack.isEmpty()?-1:stack.peek();
            stack.push(nums.get(i%n));
        }

        ArrayList<Integer> list = Arrays.stream(results) // 创建IntStream
                .boxed() // 将IntStream转换为Stream<Integer>
                .collect(Collectors.toCollection(ArrayList::new));

        return list;
    }

    /**
     * 单调栈: 单调减(从右往左)
     * @param nums
     * @return
     */
    private ArrayList<Integer> solution1111(ArrayList<Integer> nums){
        int n = nums.size();
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>(n);
        for(int i=0; i<n; i++){
            list.add(-1);
        }
        for(int i=2*n-1; i>=0; i--){
            // 单调栈 单调减(从右往左)
            while(!stack.isEmpty() && stack.peek()<=nums.get(i%n)){
                stack.pop();
            }
            list.set(i%n, stack.isEmpty()?-1:stack.peek());
            stack.push(nums.get(i%n));
        }

        return list;
    }

    /**
     * 单调栈: 单调减(从左往右)
     * @param nums
     * @return
     */
    private ArrayList<Integer> solution2(ArrayList<Integer> nums){
        int n = nums.size();
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>(n);
        for(int i=0; i<n; i++){
            list.add(-1);
        }
        for(int i=0; i<n*2; i++){
            // 单调栈 单调减(从左往右)
            while(!stack.isEmpty() && nums.get(stack.peek())<nums.get(i%n)){
                list.set(stack.pop(), nums.get(i%n));
            }
            stack.push(i%n);
        }

        return list;
    }

    /**
     * 单调栈: 单调减(从左往右)
     * @param nums
     * @return
     */
    private ArrayList<Integer> solution22(ArrayList<Integer> nums){
        int n = nums.size();
        Stack<Integer> stack = new Stack<>();
        int[] results = new int[n];
        Arrays.fill(results, -1);
        for(int i=0; i<n*2; i++){
            // 单调栈 单调减(从左往右)
            while(!stack.isEmpty() && nums.get(stack.peek())<nums.get(i%n)){
                results[stack.pop()] = nums.get(i%n);
            }
            stack.push(i%n);
        }

        ArrayList<Integer> list = Arrays.stream(results) // 创建IntStream
                .boxed() // 将IntStream转换为Stream<Integer>
                .collect(Collectors.toCollection(ArrayList::new));

        return list;
    }
}

发表于 2025-02-08 13:14:43 回复(0)

Java

isabener

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> nextBigger (ArrayList<Integer> nums) {
        // write code here
        Stack<Integer> s = new Stack<>();
        int n = nums.size();
        int[] temp = new int[n];
        for(int i=n*2-1;i>=0;i--){
            while(!s.empty()&&s.peek()<=nums.get(i%n)){
                s.pop();
            }
            temp[i%n]=s.empty()?-1:s.peek();
            s.push(nums.get(i%n));
        }
        ArrayList<Integer> res = new ArrayList<>();
        for(int i=0;i<n;i++){
            res.add(temp[i]);
        }
        return res;
    }
}

发表于 2022-03-20 19:19:14 回复(0)