数字操作

📌 核心概念

数字操作类贪心问题通常涉及数字拆分、重组、递增/递减序列构造等，核心是找到局部最优策略。

贪心策略：从高位到低位处理，或从局部最优推导全局最优。

💻 算法实现

🎯 经典应用

💡 解题技巧

📊 复杂度分析

问题	时间复杂度	空间复杂度	关键点
摆动序列	O(n)	O(1)	记录方向
单调递增数字	O(log n)	O(log n)	从高位处理
最大数	O(n log n)	O(n)	自定义排序
最大交换	O(log n)	O(log n)	贪心交换
去除重复字母	O(n)	O(1)	单调栈
拼接最大数	O(k(m+n)²)	O(k)	单调栈+合并
移掉K位数字	O(n)	O(n)	单调栈

Go 代码

// 摆动序列
func wiggleMaxLength(nums []int) int {
    n := len(nums)
    if n < 2 {
        return n
    }
 
    up, down := 1, 1
 
    for i := 1; i < n; i++ {
        if nums[i] > nums[i-1] {
            up = down + 1
        } else if nums[i] < nums[i-1] {
            down = up + 1
        }
    }
 
    return max(up, down)
}
 
// 单调递增的数字
func monotoneIncreasingDigits(n int) int {
    s := []byte(strconv.Itoa(n))
    i := 1
 
    for i < len(s) && s[i] >= s[i-1] {
        i++
    }
 
    if i == len(s) {
        return n
    }
 
    for i > 0 && s[i] < s[i-1] {
        s[i-1]--
        i--
    }
 
    for j := i + 1; j < len(s); j++ {
        s[j] = '9'
    }
 
    result, _ := strconv.Atoi(string(s))
    return result
}
 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

🎯 经典题目

题目	LeetCode	难度	关键点
摆动序列	376	中等	记录方向
单调递增的数字	738	中等	从高位处理
最大数	179	中等	自定义排序
最大交换	670	中等	贪心交换
去除重复字母	316	中等	单调栈
拼接最大数	321	困难	单调栈+合并
移掉K位数字	402	中等	单调栈

---

返回：贪心算法