单调栈的使用

• 题目：
  给定一个整数数组，返回一个数组。该返回数组中第i个数字为，原数组中第i个位置的数字至少往右走多少步才能遇到比它大的数字。如果遇不到或者已经处于最右的位置，则置为-1。

• 输入描述：
  输入为多行，第一行为一个整数N，1≤N≤106
  接下来一共有N行，每一行为一个整数M，0≤M≤232-1

• 输出描述：
  输出 N 行，每行一个数字表示转换之后的数组

• 测试用例：

输入
5
91
10
3
22
40

输出
-1
2
1
1
-1

• 思路：
  思路一：用一个双重循环，按照题目意思从当前位置往后依次遍历，直到遇到比它大的元素，简单容易理解。
  
  思路二：思路一存在时间效率上的浪费（每一个元素的查找路径都有可能存在重复的遍历），所以我们可以采用单调栈来保存记忆元素间的顺序，实现非重复的遍历损耗。
  

• 代码：

import java.util.*;

public class Main {

    public static void main(String[] args) {
	//处理数据的输入
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(sc.nextLine());
            arr[i] = x;
        }

	//初始化一个返回结果
        int[] res = new int[n];
        Arrays.fill(res,-1);

	//定义栈
        Stack<Integer> stack = new Stack<>();
	//遍历
        for (int i = 0; i < n; i++) {
	    //如果栈为空，或者当前元素不大于栈顶元素，入栈
            if(stack.isEmpty() || arr[stack.peek()]>=arr[i]){
		//这里为了判断位置关系，保存的是索引
                stack.push(i);
            }else {
		//否则，将栈内小于当前值得元素出栈
                while (arr[stack.peek()] < arr[i]){
                    int index = stack.peek();
		    //保存索引间的距离
                    res[index] = i-index;
                    stack.pop();//出栈
                }
                stack.push(i);//入栈
            }
        }

	//打印结果
        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }
    }
}