单调栈的使用

Neo
Neo
2021-09-17 / 0 评论 / 171 阅读
  • 题目:
    给定一个整数数组,返回一个数组。该返回数组中第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
  • 思路:
    思路一:用一个双重循环,按照题目意思从当前位置往后依次遍历,直到遇到比它大的元素,简单容易理解。
    image.png
    思路二:思路一存在时间效率上的浪费(每一个元素的查找路径都有可能存在重复的遍历),所以我们可以采用单调栈来保存记忆元素间的顺序,实现非重复的遍历损耗。
    image.png

  • 代码:

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]);
        }
    }
}