738. Monotone Increasing Digits

https://leetcode.com/problems/monotone-increasing-digits/

solution

• 暴力法

  • 注意如何操作位数之间

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        for i in range(n, 0, -1):
            if self.check_mono(i):
                return i
        return 0

    def check_mono(self, num):
        m = 10
        while num > 0:
            x = num % 10
            if m >= x:
                m = x
            else:
                return False
            num = num // 10
        return True

时间复杂度：O() 空间复杂度：O()

• 贪心

  • 根据规律人工剪枝，如果小于上一位，上一位减1，这一位变9. 从后往前变量利用之前结果

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        s = list(str(n))

        for i in range(len(s) - 1, 0, -1):
            if s[i-1] > s[i]:
                s[i-1] = str(int(s[i-1]) - 1)
                for j in range(i, len(s)):
                    s[j] = '9'
        return int("".join(s))

时间复杂度：O() 空间复杂度：O()

follow up

31. Next Permutation

670. Maximum Swap

# 任务: 每一位数字，找到其后面 最大的数字(相同的最大则取最远的一位）进行交换
# 有点类似单调栈, 但是从右到左，记录每一位数组中到目前见过的最大值的index

class Solution:
    def maximumSwap(self, num: int) -> int:
        nums = list(str(num))

        for i in range(len(nums)):
            max_value = nums[i] + '1'  # 一定要加1, 因为下面max_value要大于等于来选最远，但又必须比nums[i]大
            max_index = i
            for j in range(i+1, len(nums)):
                if nums[j] >= max_value:  # 注意取最大的最后一位
                    max_index = j
                    max_value = nums[j]

            if max_index > i:
                nums[i], nums[max_index] = nums[max_index], nums[i]
                return int("".join(nums))

        return int("".join(nums))

时间复杂度：O() 空间复杂度：O()

class Solution:
    def maximumSwap(self, num: int) -> int:
        digits = list(str(num))
        # 位于自己及身后的最大值index, 有相等则取最后一位, 初始化自身index
        max_digit_indices = list(range(len(digits)))

        for i in range(len(digits) - 2, -1, -1):
            # i + 1的位置已经是其后面最大的值index了, 那么只要自己小于等于最大的, 就更新为最大; 否则为自身
            # 利用了max_digit_indices的性质进行更新, 减少计算
            if digits[i] <= digits[max_digit_indices[i+1]]:
                max_digit_indices[i] = max_digit_indices[i+1]

        for i in range(len(digits)):
            max_index = max_digit_indices[i]
            if digits[i] < digits[max_index]:
                digits[i], digits[max_index] = digits[max_index], digits[i]
                break
        return int(''.join(digits))

时间复杂度：O(n) 空间复杂度：O(n)