2733. 既不是最小值也不是最大值

image-20230626074635610

解题思路：

根据题意，只需要取出3个数，求中间那个即可，操作最简单的就是，取前3个数排序之后的中间那个数

示例代码：

1
2
3
4
5
6
7
func findNonMinOrMax(nums []int) int {
    if len(nums) < 3 {
        return -1
    }
    sort.Ints(nums[:3])
    return nums[1]
}

2734. 执行子串操作后的字典序最小字符串

image-20230626075614098

解题思路:

字符a变z不会让字典序变小，操作的子串中不能包含a，替换其余字符串即可

从左到右遍历，找到第一个不为a的字符，向后继续遍历，每个字符减一，直到到了字符串末尾或者遇到了a

上述思路如果遇到全部为a的字符串会一次都不执行，题目要求必须要操作一次，所以我们把最后一个字符串变成z即可满足题意

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
func smallestString(s string) string {
    b := []byte(s)
    for i, char := range(b) {
        if char != 'a' {
            for j := i; j < len(s) && b[j] != 'a';j++ {
                b[j]--
            }
            return string(b)
        }
    }
    b[len(b)-1] = 'z'
    return string(b)
}

2735. 收集巧克力

image-20230626080820640

解题思路:

如果不操作，第i个巧克力必须花费nums[i]收集，总成本为所有nums[i]之和

如果操作一次，那么第i个巧克力话费min(nums[i], nums[i+1]%n)收集，在求和状态下，向左移或者想右移结果一致。

如果操作两次，那么第i个巧克力话费min(nums[i], nums[i+1]%n, nums[i+2]%n)收集，以此类推

定义cost数组，cost[i]表示操作k次，取到类型为i的巧克力最小花费。操作k次，总花费就等于cost数组之和，再加上k * x

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func minCost(nums []int, x int) int64 {
    n := len(nums)
    res := math.MaxInt
    cost := make([]int, n)
    for i := 0; i < n; i++ {
        cost[i] = nums[i]
    }

    for i := 0; i < n; i++ { // 执行几次操作
        curCost := 0 // 执行i次操作的花费
        for j := 0; j < n; j++ {  // 更新每个位置巧克力能够取到的最小花费
            cost[j] = min(cost[j], nums[(j+i)%n])
            curCost += cost[j]
        }
        res = min(res, curCost + i * x)
    }
    return int64(res)
}
func min(a, b int) int { if b < a { return b }; return a }

2736.最大和查询

image-20230627075052946

解题思路:

将 nums1 和 queries 中的xix_i排序，这样我们就只需要关注 nums2[j] 与 yiy_i 的大小关系上即可。按照 xix_i 从大到小，nums1[j] 从大到小的顺序处理，同时增量的维护满足 nums1[j]≥xinums1[j] \geq x_i 的 nums2[j]

维护方式：

如果 nums2[j] 比之前遍历过的 nums2[j‘] 还要小，那么由于 nums2[j] 是从大到小处理的，所以 nums1[j]+nums2[j] 比之前遍历过的 nums1[j’]+nums2[j‘] 要小。那么在回答 <=nums2[j] 的 yiy_i 时，最大值不可能是 nums1[j]+nums2[j]，所以无需考虑这样的 nums2[j]。（这种单调性启发我们用单调栈来维护。）

如果是相等，那么同理，无需考虑。

如果是大于，那么就可以入栈。在入栈前还要去掉一些无效数据：

​ 如果 nums1[j]+nums2[j]不低于栈顶的 nums1[j’]+nums2[j‘]，那么可以弹出栈顶。因为更大的nums2[j]更能满足 ≥yi\geq y_i的要求，栈顶的 nums1[j’]+nums2[j‘] 在后续的询问中，永远不会是最大值

​ 代码实现时，可以直接比较nums1[j]+nums2[j]与栈顶的值，这是因为如果这一条件成立，由于 nums1[j]是从大到小处理的，nums1[j]+nums2[j] 能比栈顶大，说明 nums2[j] 必然必定与栈顶的 nums2[j']

这样我们会得到一个从栈底到栈顶，nums2[j] 递增，nums1[j]+nums2[j] 递减的单调栈

最后在单调栈中二分 ≥yi\geq y_i 的最小 nums2[j]，对应的nums1[j]+nums2[j] 就是最大的。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func maximumSumQueries(nums1 []int, nums2 []int, queries [][]int) []int {
    type pair struct {
        x, y int
    }

    // x从小到大排序
    pairList := make([]pair, len(nums1))
    for i, x := range nums1 {
        pairList[i] = pair{x, nums2[i]}
    }
    sort.Slice(pairList, func(i, j int) bool { return pairList[i].x < pairList[j].x })

    for i := range queries {
        queries[i] = append(queries[i], i) // 将下标加入queries
    }
    // 查询从小到大排序
    sort.Slice(queries, func(i, j int) bool { return queries[i][0] > queries[j][0] })

    ans := make([]int, len(queries))
    var stack []pair
    i := len(pairList) - 1
    for _, query := range queries {
        for i >= 0 && pairList[i].x >= query[0] {
            for len(stack) > 0 && stack[len(stack)-1].y <= pairList[i].x+pairList[i].y { // 栈顶小于当前值,弹出
                stack = stack[:len(stack)-1]
            }
            if len(stack) == 0 || stack[len(stack)-1].x < pairList[i].y { // 栈顶大于当前值,压入
                stack = append(stack, pair{pairList[i].y, pairList[i].x + pairList[i].y})
            }
            i--
        }

        j := sort.Search(len(stack), func(i int) bool { return stack[i].x >= query[1] })
        if j < len(stack) {
            ans[query[2]] = stack[j].y
        } else {
            ans[query[2]] = -1
        }
    }
    return ans
}