Envío 6607

Código

import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int casosDePrueba = scanner.nextInt();

        for(int caso=1; caso<=casosDePrueba; caso++){
            int n = scanner.nextInt();

            HashMap<Integer, Integer> memoization = new HashMap<Integer, Integer>();
            Stack<Key> stack = new Stack<Key>();
            for(int i=0; i<n; i++){
                int height = scanner.nextInt();
                while (!stack.isEmpty() && stack.peek().getHeight() < height) {
                    Key key = stack.pop();
                    memoization.put(key.getIndex(), height);
                }
                stack.add(new Key(i, height));
            }

            System.out.print("Case #" + caso + ":");
            for(int i=0; i<n; i++){
                if(memoization.containsKey(i)){
                    System.out.print(" " + memoization.get(i));
                } else {
                    System.out.print(" -1");
                }
            }

            System.out.println();
        }
    }

//    /**
//     * This doesn't work for this problem.
//     * I need the successor(x) to be to the first index i after x where value(i) > value(x)
//     * @param start
//     * @param array
//     * @return
//     */
//    private static int findMaxSuffixArray(int start, int[] array){
//        if(memoization.containsKey(start)){
//            return memoization.get(start);
//        }
//
//        if(start == array.length){
//            memoization.put(start, -1);
//            return -1;
//        }
//
//        int value = array[start];
//        int recResponse = findMaxSuffixArray(start+1, array);
//
//        int max = Math.max(value, recResponse);
//        memoization.put(start, max);
//        return max;
//    }

    private static class Key{
        private int index;
        private int height;

        public Key(int index, int height) {
            this.index = index;
            this.height = height;
        }

        public int getIndex() {
            return index;
        }

        public int getHeight() {
            return height;
        }
    }
}