侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-02-05 / 0 评论 / 0 点赞 / 102 阅读 / 620 字
温馨提示:
本文最后更新于 2023-02-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

百亿富翁 - 蓝桥云课


问题描述

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

已知这排楼房一共有 NN 栋,编号分别为 1N1 \sim N,第 ii 栋的高度为 hih_i

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

输入格式

11 行输入一个整数 NN,表示楼房的数量。

22 行输入 NN 个整数(相邻整数用空格隔开),分别为 h1,h2,,hNh_1, h_2, \dots, h_N, 表示楼房的高度。

1N7×105,1hi1091 \le N \le 7 \times 10 ^5, 1 \le h_i \le 10^9

输出格式

输出共两行。

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

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

样例输入

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

评论区