• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

数组左边和右边离i最近的比arr[i]小的位置

开发技术 开发技术 4天前 6次浏览

链接
给定一个可能含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。

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

public class Main {

    private static final StreamTokenizer TOKENIZER =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    private static int nextInt() {
        try {
            TOKENIZER.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) TOKENIZER.nval;
    }

    private static int[][] solve(int[] arr) {
        int n = arr.length;
        int[][] ret = new int[n][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; ++i) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                ret[stack.pop()][1] = i;
            }
            ret[i][0] = stack.isEmpty() ? -1 :
                    (arr[i] == arr[stack.peek()] ? ret[stack.peek()][0] : stack.peek());
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            ret[stack.pop()][1] = -1;
        }
        return ret;
    }

    private static void print(int[][] ret) {
        StringBuilder sb = new StringBuilder();
        for (int[] item : ret) {
            sb.append(item[0]).append(" ").append(item[1]).append("n");
        }
        System.out.println(sb);
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = nextInt();
        }
        int[][] ret = solve(arr);
        print(ret);
    }
}

程序员灯塔
转载请注明原文链接:数组左边和右边离i最近的比arr[i]小的位置
喜欢 (0)