最近的较小值

发表于 分类于 Waline： 本文字数： 1.1k 阅读时长 ≈ 2 分钟

Do not let your emotions override you judgement. ——《惊奇队长》

别让情绪干扰了你的理智和判断力。

问题

  让函数 NearestSmallerValues(arr) 接受一个存储在 arr 中的整数数组，并为列表中的每个元素搜索它本身所有先前值，以查找小于当前元素的最近元素，并从这些数字创建一个新列表。如果在某个较小位置之前没有元素，则在新列表中当前位置的值为 -1 。
  例如：如果 arr 为[ 5, 2, 8, 3, 9, 12 ]，则最接近的较小值列表为[-1, -1, 2, 2, 3, 9]。
  逻辑如下：对于5，没有较小的先前值，因此到目前为止的列表为[-1]。对于2，也没有较小的先前值，因此列表现在为[-1，-1]。对于8，距离最近的较小值为2，因此列表现在为[-1, -1, 2]。对于3，最近的较小值也是2，因此列表现在为[-1, -1, 2, 2]。以此类推。程序最终以空格分隔的字符串的形式输出：-1 -1 2 2 3 9

例子

1
2
输入：[5, 3, 1, 9, 7, 3, 4, 1]
输出：-1 -1 -1 -1 1 1 3 1
1
2
输入：[2, 4, 5, 1, 7]
输出：-1 2 4 -1 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def NearestSmallerValues(arr):
    new_list = [-1]
    for i in range(1, len(arr)):
        if arr[i] > arr[i-1]:
            new_list.append(arr[i - 1])
        else:
            for j in range(i - 1, -1, -1):
                if arr[i] > arr[j] or arr[i] == arr[j]:
                    new_list.append(arr[j])
                    break
            else:
                new_list.append(-1)
    return ' '.join(list(map(str, new_list)))


print(NearestSmallerValues([5, 3, 1, 9, 7, 3, 4, 1]))

输出：

1
>>> -1 -1 -1 1 1 1 3 1

思路

  1. 对于列表的第一个元素，因为在它前面没有比他小的值，所以直接赋值为-1
  2. 从列表第二个元素开始循环，如果下标为 i 的元素大于下标为 i - 1 的元素，那么新列表中 i 位置的值为 arr[i - 1]
  3. 否则，继续往前找比当前值小于或等于的值，找到较小值后添加到新列表中
  4. 如果下标为 i 的元素没有较小的先前值，那么新列表中 i 位置的值为 -1
  5. 将列表转换为以空格分隔的字符串的形式

PS: 如果您发现文中有错误、思路不够清晰等问题或者您有更优解，都可以在下方留言！！！