Check if an Array Is Sorted
给定一个整数数组 nums。如果它按非递减顺序排列，也就是说，每个元素都小于或等于它后面的元素，则返回 true，否则返回 false。相邻元素相等也没问题：[2, 2, 3] 算作已排序。只有一个元素的数组也算已排序。
函数
- numsinteger-array
- 要检查的整数数组
- 返回值boolean
- 当每个元素都小于或等于下一个元素时为 true，否则为 false
约束条件
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
示例
- 输入
- nums = [1, 3, 3, 7]
- 输出
- true
- 解释
- 每一步都向上或保持不变：从 1 到 3，从 3 到 3，从 3 到 7。重复出现 3 是允许的，所以答案是
true。
- 输入
- nums = [2, 5, 4, 9]
- 输出
- false
- 解释
- 从 5 到 4 是递减的，这样的一步就会让数组变得无序，尽管末尾的 9 是最大值。
进阶
如何用一次遍历检查一个可能按升序或降序排列的数组？
提示
逐个打开提示，每个都会多透露一点。
如果数组没有排序，你能从哪里看出来？你需要比较相距很远的元素吗？
只需将每个元素与紧随其后的元素进行比较即可。相邻元素可以相等，只有出现下降才会打破顺序。
遍历相邻的数对，在第一个左侧值大于右侧值的数对处返回
false。如果不存在这样的数对，则返回true。
题解
当没有任何元素大于紧随其后的元素时，数组就已经排好序了。因此，只需检查 n-1 对相邻元素，就能判断数组是否排好序，并且遇到第一处下降时就可以停止检查。
对副本排序并进行比较
思路
如果排序后数组不会发生变化，这个数组就是已排序数组：对副本进行排序，再逐个位置与 nums 比较。对于 [2, 5, 4, 9]，副本 [2, 4, 5, 9] 在位置 1 处不同，所以答案是 false。
排序的时间复杂度为 O(n log n)，对 5000 个数字来说，大约需要 6 × 10^4 次比较；此外，副本还需要 O(n) 的内存。即使第一对数字已经顺序错误，排序仍会读取整个数组。
算法
- 复制
nums，这样原列表就不会改变。 - 按数值从小到大的顺序对副本进行排序。
- 逐个位置比较副本和
nums。 - 如果每个位置都匹配，则返回
true，否则返回false。
def isSorted(nums):
# sorted returns a new list, so nums itself is left as it was.
return sorted(nums) == nums比较每一对相邻元素
思路
由于 ≤ 具有传递性（a ≤ b 且 b ≤ c 可以推出 a ≤ c），n-1 个相邻位置对就涵盖了所有位置对，而未排序的数组总有一对相邻元素是递减的。因此，让 i 从 1 遍历到 n-1，遇到第一个 nums[i-1] > nums[i] 时就返回 false。对于 [2, 5, 4, 9]，这对元素是（5，4），而 9 永远不会被读取。相邻元素相等时会通过检查，因为只有 > 才会导致失败。
每对元素只比较一次：时间复杂度为 O(n)，空间复杂度为 O(1)。
算法
- 让
i从 1 循环到n-1。 - 如果
nums[i-1] > nums[i]，返回false。 - 如果循环结束，返回
true。只有一个元素时会跳过循环，并且该序列已排序。
def isSorted(nums):
for i in range(1, len(nums)):
# One step down anywhere breaks the order.
if nums[i - 1] > nums[i]:
return False
return True
易错点和边界情况
- 把相等的相邻元素视为失败。测试
nums[i-1] >= nums[i]会拒绝[1, 3, 3, 7]。 - 越界读取。从
0到n-1的循环若将nums[i]与nums[i+1]比较，会在最后一步读取数组范围之外的内容。从i = 1开始，并与i-1比较。 - 用减法代替比较。
nums[i] - nums[i-1] >= 0在[-1000000000, 1000000000]上会导致 32 位 int 溢出：2 × 10^9会变成负数，于是数组会被报告为未排序。用x - y编写的 qsort 比较函数也会出现同样的问题。 - 把数字当作文本排序。在 JavaScript 中，不带比较函数的
sort()会把10排在9前面，所以先排序再比较会得到错误答案。
常见问题3
如何检查数组是否已排序？
将每个元素与下一个元素比较。如果某个元素大于它右边的元素，数组就没有排序，你可以停止；如果一直检查到末尾都没有发现这样的元素，数组就是已排序的。这需要 O(n) 时间和 O(1) 额外空间。
元素相同的数组是有序的吗？
是的，它按非递减顺序排列：[4, 4, 4] 已排序，因为没有元素大于它后面的元素。如果题目要求按严格递增顺序排列，则要修改测试，使其也拒绝相邻元素相等的情况。
我可以对副本进行排序，并将它与原始内容进行比较吗？
是的，它能给出正确答案，但需要 O(n log n) 的时间和 O(n) 的额外内存。检查相邻元素不需要复制，也可以在第一次下降时停止。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def isSorted(nums):
# 在这里编写代码测试 #1
测试 #2
参数
nums = [1, 3, 3, 7]
预期输出
true