第一章 栈和队列（单调栈结构）

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

输入描述:
第一行输入一个数字 n，表示数组 arr 的长度。
以下一行输入 n 个数字，表示数组的值

输出描述:
输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。

示例：

输入
7
3 4 1 5 6 2 7

输出
-1 2
0 2
-1 -1
2 5
3 5
2 -1
5 -1

    public static void main(String[] args) {Integer[] arr = {3, 4, 1, 5, 6, 2, 7};int[][] ints1 = noRepeat(arr);for (int[] ints : ints1) {System.out.println(String.format("(%s,%s)", ints[0], ints[1]));}}static int[][] noRepeat(Integer[] arr) {// 存放数组下标值Stack<Integer> indexStack = new Stack<Integer>();// 存放返回结果int[][] res = new int[arr.length][2];for (int i = 0; i < arr.length; i++) {//while (!indexStack.isEmpty() && arr[indexStack.peek()] > arr[i]) {Integer cur = indexStack.pop();int leftLessIndex = indexStack.isEmpty() ? -1 : indexStack.peek();res[cur][0] = leftLessIndex;res[cur][1] = i;}indexStack.add(i);}while (!indexStack.isEmpty()) {Integer cur = indexStack.pop();int leftLessIndex = indexStack.isEmpty() ? -1 : indexStack.peek();res[cur][0] = leftLessIndex;res[cur][1] = -1;}return res;}

(-1,2)
(0,2)
(-1,-1)
(2,5)
(3,5)
(2,-1)
(5,-1)