今日题目

https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/description/

直觉

如果数组经过了轮转，那么将原数组拼接两次后，其中必然包含一段完整的有序原数组。

技巧

将原数组拼接到自身末尾，相当于构造了一个环形结构。

思路

  • 将 nums 拼接到自身末尾。
  • 然后检查其中是否存在长度至少为 N 的非递减子序列。

复杂度

  • 时间复杂度：$O(N)$，N 为数组长度

  • 空间复杂度：$O(1)$

代码

class Solution:
    def check(self, nums: List[int]) -> bool:
        n = len(nums)
        nums += nums
        cnt = 1
        pre = nums[0]
        for num in nums[1::]:
            if num >= pre:
                cnt += 1
            else:
                cnt = 1
            pre = num

            if cnt >= n:
                return True
        

        return False

image.png