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
# 任务: 每一位数字,找到其后面 最大的数字(相同的最大则取最远的一位)进行交换
# 有点类似单调栈, 但是从右到左,记录每一位数组中到目前见过的最大值的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)
Last updated