单调递增的数字 & 最大交换 & 有效的括号字符串 & 分发糖果 & 下一个排列——贪心

Author： SnowKagura
发布时间：July 10, 2025
10 views
No comments
2604 words
Categories： Leetcode

# 单调递增的数字

这道题完全是用贪心的策略去修改对应位的数字，贪心规则如下：

从最小位开始向前遍历，如果前一位数字大于后一位数字，前一位数字-1，并且标记当前位，后续把标记位以及之后的位置全部变成9，就是距离给定数字最近的单调递增数字。

```go
func monotoneIncreasingDigits(n int) int {
    s := []byte(strconv.Itoa(n))
    pos := -1
    for i := len(s)-1; i > 0; i-- {
        if s[i-1] > s[i] {
            s[i-1]--
            pos = i
        }
    }
    if pos != -1 {
        for i := pos; i < len(s); i++ {
            s[i] = '9'
        }
    }
    res, _ := strconv.Atoi(string(s))
    return res
}
```

# 最大交换

这个题目也是贪心，需要从后往前找到数字大的换到前面尽可能靠近最大位，所以我们先记录右侧每位最大值的位置，然后在每个位置去看有没有比当前位置大的且在后面的，如果有就交换返回即可。

```go
func maximumSwap(num int) int {
    str := []byte(strconv.Itoa(num))
    last := [10]int{}
    for i, v := range str {
        last[v-'0'] = i
    }
    for i := range str {
        for d := 9; d > int(str[i]-'0'); d-- {
            if last[d] > i {
                str[last[d]], str[i] = str[i], str[last[d]]
                res, _ := strconv.Atoi(string(str))
                return res
            }
        }
    }
    return num
}
```

# 有效的括号字符串

这个题因为多了一个万能的 * 字符，单个栈做是做不了了，除非把 * 看作多种可能的字符串都给列出来一个个计算，这就需要用到回溯，而且计算量明显是很大的，所以可以用贪心的方法，配合两个变量进行计数。

我们定义 low 为 * 全部看成 ) 的最少多余左括号，high 为 * 全部看作 ( 的最多多余左括号。

那么有以下规则：

- 遇到 ( 时，low和high都增加。
- 遇到 ) 时，low 和 high 都减少，控制 low 最小为 0。
- 遇到 * 时，low 大于零可以减一，high则可以加1。

一旦 high 小于 0，说明右括号多到连 * 都兜不住底了，那么就肯定无效，如果 low 大于 0，说明原本的左括号多到 * 兜不住底，也是无效。

根据上述逻辑，写出代码如下：

```go
func checkValidString(s string) bool {
    // low 代表*为)可拥有的(个数
    // high 代表*为(可拥有的(个数
    // 那么最终 low==0，则说明有效
    low, high := 0, 0
    for i := range s {
        switch s[i] {
        case '(':
            low++
            high++
        case ')':
            if low > 0 {
                low--
            }
            high--
        case '*':
            if low > 0 {
                low--
            }
            high++
        }
        if high < 0 {
            return false
        }
    }
    return low == 0
}
```

# 分发糖果

这道题也是贪心做法，从左往右和从右往左分别扫描一遍，保证比左边大的得到的糖果更多，比右边大的得到的糖果更多，就能保证满足题意规则。

```go
func candy(ratings []int) int {
    n := len(ratings)
    candies := make([]int, n)
    for i := range candies {
        candies[i] = 1
    }
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1
        }
    }
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] && candies[i] <= candies[i+1] {
            candies[i] = candies[i+1] + 1
        }
    }
    res := 0
    for _, v := range candies {
        res += v
    }
    return res
}
```

# 下一个排列

这道题想要得到下一个更大的排列，也算是贪心做法，就是需要从后往前找递增的i和i+1，然后再从后往前找比nums[i]大的j，交换nums[i]和nums[j]，相当于换了一个较小的数到前边，然后再把降序的nums[i+1:]进行反转，就是下一个排列了。

```go
func nextPermutation(nums []int)  {
    n := len(nums)
    i := n-2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }
    if i >= 0 {
        j := n-1
        for j >= 0 && nums[j] <= nums[i] {
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    reverse(nums[i+1:])
}

func reverse(nums []int) {  
    for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
        nums[i], nums[j] = nums[j], nums[i]
    }
}
```

Last modification：July 20, 2025