Leetcode【31、162】

问题描述：【Math】31. Next Permutation

解题思路：

这道题是给一个数组，表示一个排列。求比当前排列大的下一个排列。如果没有则返回最小排列。

这道题需要找规律：

• （1）对于 [6,1,2,3] 这种，很明显只需要交换最后两个数字即可。
• （2）对于 [2,3,2,1] 和 [10,6,5,7,3] 这种，需要两步操作：第一步，从后往前遍历数组，找到降序序列（分别是 [3,2,1] 和 [7,3]），并记录第一个不符合降序序列的数字 num （分别是 2 和 5），将降序序列按照升序排列（分别是 [1,2,3] 和 [3,7]）；第二步，在刚刚排好的升序序列中，找到第一个比数字 num （分别是 2 和 5）大的数字，进行交换即可（分别是 [3,1,2,2] 和 [10,6,7,3,5]）。
• （3）对于 [6,5,4,3,2,1] 这种，在从后往前遍历数组时，找到了完整的降序序列，因此没有比该排列大的下一排列了。这时只需要 nums.reverse()，返回最小排列即可。
• （4）注意观察 （1）、（2）可以合并成（2）这一种情况。

无论是对降序序列按照升序序列排序还是交换两个数，都可以在原数组上进行，因此空间复杂度为 O(1)，时间复杂度为 O(n^2)。当然，还可以使用二分查找的思想加快（2）中第二步的速度。

Python3 实现：

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        lens = len(nums)
        for i in range(lens-2, -1, -1):  # 从后往前遍历找降序子序列
            if nums[i] < nums[i+1]:
                # 1、将降序的 [i+1, lens-1] 按照升序排列
                j, cnt = i + 1, 0
                while cnt < (lens - i - 1) // 2:
                    nums[j], nums[lens-1-cnt] = nums[lens-1-cnt], nums[j]
                    j += 1
                    cnt += 1
                # 2、在升序的 [i+1, lens-1] 中找到第一个比 nums[i] 大的数字，交换它们
                for k in range(i+1, lens):
                    if nums[k] > nums[i]:
                        nums[i], nums[k] = nums[k], nums[i]
                        return
        else:  # 肯定是降序
            nums.reverse()
            return

问题描述：【Binary Search】162. Find Peak Element

解题思路：

寻找峰值。给一个数组，峰值元素是指其值大于左右相邻值的元素，峰值可能有多个，找到其中一个峰值元素对应索引。假设数组前后均为负无穷。

首先，数组前后均为负无穷可以保证峰值元素一定存在。这道题可以使用二分查找的思想：

• （1）对于 nums = [1,2,3,2,1]，如果 nums[mid] 比前后两个元素都要大，则 mid 就应该是答案；
• （2）对于 nums = [1,4,3,2,1]，如果 nums[mid] 比左边的小、比右边的大，则说明峰值元素应该在左区间，high = mid - 1；
• （3）对于 nums = [1,2,3,4,1]，如果 nums[mid] 比左边的大、比右边的小，则说明峰值元素应该在右区间，low = mid + 1；
• （4）对于 nums = [5,4,3,4,5]，如果 nums[mid] 比前后两个元素都要小，则将这种情况随便归为（2）、（3）其中一种即可。因为数组前后均为负无穷可以保证峰值元素一定存在。

因为要比较 nums[mid] 的相邻左右两个元素，因此需要注意边界。可以对边界单独判断。即如果存在 [6,4,...] 或者 [...,4,5] 这种，则可以直接返回 0 或者 len(nums) - 1，因为数组前后均为负无穷， 6 或者 5 就可以视为峰值。

时间复杂度就是二分查找的复杂度，即 O(log n)。

Python3 实现：

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        lens = len(nums)
        if lens == 1 or nums[0] > nums[1]: return 0  # 边界处理
        if nums[-1] > nums[-2]: return lens - 1  # 边界处理
        low, high = 0, lens - 1
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1]:  # 找到峰值元素
                return mid
            elif nums[mid] < nums[mid-1] and nums[mid] > nums[mid+1]:  # 在右侧寻找
                high = mid - 1
            else:   # 在左侧寻找
                low = mid + 1