蓝桥杯LV1 - 百亿富翁（找左右第一个更大元素｜暴力写法）

/* 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

解题思路

暴力思路（好理解）
 
1. 遍历每一栋楼
2. 找左边：从它左边紧邻的楼，往左边倒着找，一旦遇到第一个比它高的，记录编号，立刻停止，找不到就记 -1（刚开始就给了-1）
3. 找右边：从它右边紧邻的楼，往右边顺着找，一旦遇到第一个比它高的，记录编号，立刻停止；找不到就记 -1

完整代码

#include <stdio.h>

#include <stdlib.h>

long long h[700005];

int L[700005],R[700005];

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

{

  long long n;

  scanf("%lld",&n);

  int i;

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

  {

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

  }

  int j;

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

  {

     L[i]=-1;

    for(j=i-1;j>=1;j–)

    {

      if(h[j]>h[i])

      {

        L[i]=j;

        break;

      }

    }

  }

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

  {

    R[i]=-1;

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

    {

      if(h[j]>h[i])

      {

        R[i]=j;

        break;

      }

    }

  }

  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. 找左边的时候，j 要  j–  往回倒着搜，之前我写成  j++  向右走，永远找不到正确答案
2. 数组初始值一定要手动赋值  -1 ，全局数组默认是0，会和编号混淆
3. 找到符合条件的楼房一定要  break ，不然会覆盖成最远的高楼，不是"第一个"
4. 这个暴力只能过小数据，N几十万的时候会超时，本题考点是单调栈（我下一篇发）