【单调栈】百亿富翁【蓝桥杯】

题目

百亿富翁 - 蓝桥云课

---

问题描述

这天小明买彩票中了百亿奖金，兴奋的他决定买下蓝桥公司旁的一排连续的楼房。

已知这排楼房一共有 $N$ 栋，编号分别为 $1 \sim N$，第 $i$ 栋的高度为 $h_i$。

好奇的小明想知道对于每栋楼，左边第一个比它高的楼房是哪个，右边第一个比它高的楼房是哪个（若不存在则输出 $−1$）。但由于楼房数量太多，小明无法用肉眼直接得到答案，于是他花了 $1$ 个亿来请你帮他解决问题，你不会拒绝的对吧？

输入格式

第 $1$ 行输入一个整数 $N$，表示楼房的数量。

第 $2$ 行输入 $N$ 个整数（相邻整数用空格隔开），分别为 $h_1, h_2, \dots, h_N$, 表示楼房的高度。

$1 \le N \le 7 \times 10 ^5, 1 \le h_i \le 10^9$。

输出格式

输出共两行。

第一行输出 $N$ 个整数，表示每栋楼左边第一栋比自己高的楼的编号。

第二行输出 $N$ 个整数，表示每栋楼右边第一栋比自己高的楼的编号。

样例输入

5
3 1 2 5 4

样例输出

-1 1 1 -1 4
4 3 4 -1 -1

运行限制

• 最大运行时间：2s
• 最大运行内存：256M

解题

方法一：单调栈

思路

单调栈模板题，思路见：【单调栈】单调栈「单调栈经典应用」。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        int[] stk = new int[n + 1];
        int top = 0;
        for (int i = 1; i <= n; ++i) {
            while (top > 0 && a[stk[top]] <= a[i]) --top;
            System.out.print(top == 0 ? "-1 " : stk[top] + " ");
            stk[++top] = i;
        }
        System.out.print("\n");
        top = 0;
        int[] tmp = new int[n + 1];
        for (int i = n; i >= 1; --i) {
            while (top > 0 && a[stk[top]] <= a[i]) --top;
            tmp[i] = top == 0 ? -1 : stk[top];
            stk[++top] = i;
        }
        for (int i = 1; i <= n; ++i) System.out.print(tmp[i] + " ");
    }
}