【字节】- 山形数组

题目

山形数组定义如下：
一维数组，数组元素从左到右逐渐变大，达到某个最大值后，又开始逐渐缩小。
例如：1，2，2，5，10，9，8，2，1，1
要求按照元素从小到大顺序，不重复输出，上面case的输出为1，2，5，8，9，10。
要求时间复杂度O(n)，空间复杂度O(1)。

思路

双指针

代码最少的方法：set去重后排序

代码

def mountainArrays(nums):
    left, right = 0, len(nums) - 1
    ans = []
    while left <= right:
        if ans and nums[left] == ans[-1]:
            left += 1
        elif ans and nums[right] == ans[-1]:
            right -= 1
        elif nums[left] == nums[right]:
            ans.append(nums[left])
            left += 1
            right -= 1
        elif nums[left] < nums[right]:
            ans.append(nums[left])
            left += 1
        elif nums[left] > nums[right]:
            ans.append(nums[right])
            right -= 1
    return ans
nums = [int(i) for i in input().split()]
print(mountainArrays(nums))