738.单调递增的数字

链接：738.单调递增的数字
难度：Medium
标签：贪心、数学
简介：给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

题解 1 - typescript

• 编辑时间：2020-12-15
• 执行用时：88ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：检测到第一位非递增位，后续置 9。

function monotoneIncreasingDigits(N: number): number {
  const arr: number[] = N.toString()
    .split('')
    .map(v => +v);
  const len = arr.length;
  let i = 1;
  while (i < len && arr[i - 1] <= arr[i]) i++;
  if (i === len) return N;
  while (i > 0 && arr[i - 1] > arr[i]) {
    arr[i - 1]--;
    i--;
  }
  for (i += 1; i < len; i++) {
    arr[i] = 9;
  }
  return arr.reduce((total, cur) => total * 10 + cur, 0);
}