蓝桥杯LV1 - 百亿富翁（单调栈AC版）

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

题目描述

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

已知这排楼房一共有 N 栋，编号分别为 1∼N，第 i 栋的高度为 hi​。

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

输入描述

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

第 2 行输入 N 个整数（相邻整数用空格隔开），分别为 h1,h2,…,hN，表示楼房的高度。

1≤N≤7×10^5，1≤hi≤10^9

输出描述

输出共两行。

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

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

输入输出 样例

输入

5

3 1 2 5 4

输出

-1 1 1 -1 4

4 3 4 -1 -1

解题思路

暴力写法两层循环，当 N 最大为700005时会超时，因此使用单调栈（等候区思想）
核心：开辟一块等候区（数组st配合top标记），等候区里面只保留有可能成为后面楼房答案的高楼
只要等候区最顶部楼房高度 ≤ 当前楼房高度，说明等候区顶部楼房被挡住、后面的楼再也看不到它，可以直接移出等候区。

 
步骤：

1. 从左向右遍历所有楼房，求出每一栋楼左边第一个更高楼房编号
2. 将等候区清空，从右向左遍历所有楼房，求出每一栋楼右边第一个更高楼房编号
3. 按格式输出两组答案

变量说明

 h[] ：存储每一栋楼的高度
 L[] ：L[i]保存i号楼左边第一个更高楼编号
 R[] ：R[i]保存i号楼右边第一个更高楼编号
 st[] ：等候区数组，存放楼房编号（实现单调栈）
 top ：等候区顶部标记，top=0代表等候区为空

注意:代码中的st[top]整体始终是一个下标，它不是高度的值，它是h某个位置的下标，不要看它是个数组误以为是数值

完整代码

#include <stdio.h>

#include <stdlib.h>

long long h[700005];//高度

int L[700005],R[700005];//左右

int st[700005];//栈

int top;//栈标记

int main(int argc, char *argv[])

{

  long long n;

  scanf("%lld",&n);

  int i;

  for(i=1;i<=n;i++)

  {

    scanf("%lld",&h[i]);

  }

  top=0;//目前在最底层

  for(i=1;i<=n;i++)//处理左边

  {

    while(top&&h[st[top]]<=h[i])//当前层比要找的还小丢掉，比要找的大了就直接退出了

      top–;//就直接丢掉，丢完了就退出了

    L[i]=top?st[top]:-1;//top>0证明h[i]左边有比它大的，st[top]就是大的那个,=0就是没有找到

    st[++top]=i;//处理下一个h[i]

    //这一条必须写在这里，因为最边上(i=1)是不需要处理的

  }

  top=0;

  for(i=n;i>=1;i–)//找右边最高的楼

  {

    while(top&&h[st[top]]<=h[i])//这里不需要改,因为循环条件的更改，现在逻辑和找左边一样

      top–;

    R[i]=top?st[top]:-1;

    st[++top]=i;

  }

  for(i=1;i<=n;i++)//输出找到的左边的

  {

    if(i>1)

      printf(" ");

    printf("%d",L[i]);

  }

  printf("\\n");//一定不能忘，题目要求了输出是两行

    for(i=1;i<=n;i++)//输出找到的右边的

  {

    if(i>1)

      printf(" ");

    printf("%d",R[i]);

  }

  return 0;

}

踩坑记录

1.输出时两行答案之间必须写  printf("\\n"); ，不换行就不符合题目输出格式要求
2.while判断条件的符号：本题要找比当前更高，所以等候区顶部 ≤ 当前楼就弹出；如果换题找更小元素，需要修改判断符号