53.Tom跳方格

题目概述

题目详情(点我)

现在有n个方格(1<=n<=1e5)，每个方格都有不同的高度h1,h2,h3…hn(1<=hi<=1e9)，Tom最喜欢跳方格了，刚开始他可以任意选一个方格作为起点，只要他右边的方格没有当前的方格的高度高，他就会不断的往右边的方格去跳，请帮助Tom计算一下他最多能跳多少个方格。

输入:
输入方格总数n(1<=n<=1e5)，和n个数h1,h2,h3…hn表示每个方格的高度

输出:
输出Tom能连续跳的最大长度

题解

解题方法

• 求最长序列

算法知识

• 数组

  • 时间复杂度: n
  • 空间复杂度: 1

解题思路

• Tom可以从不同位置开始跳
  换句话说, 题目求的就是 最长的非递增序列, 所以我们要做的就是将所有最长的非递减序列求出来。

• 是否需要求出所有的非递减序列呢？
  答案是不需要: 我们只要最长的非递减序列。
  如: 5 4 3 3 2 4 3 2 1, 在这个序列中就有两个最长非递增序列 (5 4 3 3 2) 和 (4 3 2 1), 所以我们只需要在一个非递增序列的末端就可以开始计算下一个最长非递增序列了。然后再判断当前的序列是否比上一个序列更长。

审题

• int[] nums : 存储每个方格的高度
• n : 有n个方格

题目要求

• 求连续跳的最大长度 [求最长的非递增子序列]

解题步骤

1. 设置变量result、len, 分别用来存储最终长度和一段最长序列的长度, 初始化为0

2. 从第一个方块开始循环遍历数组, 选出最长的非递减序列

   • 若nums[i] >= nums[i+1], 则len加1; (i ∈ [0, n-2])
   • 若nums[i] < nums[i+1], 则将len与result比较, 将两个变量的最大值赋值给result;
3. 循环结束后, 还必须对len和result进行比较。因为可能在最后一次循环时, 没有将len和result进行对比, 有可能最后一段序列是最长的，但是却没有对齐进行判断。所以循环结束后还得再比较一次。