题解 | #交换到最大#

题目链接

交换到最大

题目描述

给定一个仅由数字 0-9 构成的字符串 s。你可以执行无限次如下操作：

选择 s 中一个既不是最左端、也不是 '0' 的字符 s[i]。
将该字符的数值减 1。
将该字符与它左侧的相邻字符交换位置。

目标是求出通过以上操作能够得到的字典序最大的字符串。

解题思路

为了获得字典序最大的字符串，我们应采取贪心策略，从左到右依次确定结果字符串的每一位，并使每一位的数字尽可能大。

1. 贪心策略与关键洞察

对于结果字符串的第 i 位，我们需要从其右侧（包括自身）选择一个字符 s[j] (j >= i)，通过操作将其移动到 i 位置。当 s[j] 被移动到 i 位置时，它需要向左移动 j-i 次，其最终值会变为 s[j] - (j - i)。

这里的关键洞察在于，任何距离当前位置超过 9 的字符，移动过来的价值都必然是负数，不可能比不移动更优。因此，在为第 i 位寻找最佳字符时，我们只需要在一个大小至多为10的滑动窗口内（即从索引 i 到 min(i+9, n-1)）进行搜索。

2. 算法步骤

正确的贪心算法如下：

从左到右遍历字符串，用索引 i 表示我们正在确定最终结果的第 i 位。
寻找最优：对于每个 i，在其后的一个固定大小窗口 [i, min(i+9, n-1)] 内寻找一个最佳的字符来源位置 best_pos。
- “最佳”指的是能使 s[j] - (j-i) 这个值最大的那个 j。我们将这个最大值记为 best_val。
物理移动：将 best_pos 位置的字符通过一系列交换，物理地移动到 i 位置。这一步的目的是正确地重排字符串，为后续步骤提供正确的字符池。
更新数值：（最关键的一步） 将 i 位置的字符赋值为我们在第二步中计算出的最优价值 best_val。
重复此过程，直到 i 遍历完整个字符串。

这个算法的每次决策只涉及一个常数大小的窗口，因此总时间复杂度为 $\mathcal{O}(N)$ 。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    string s;
    cin >> s;
    int n = s.length();

    for (int i = 0; i < n; ++i) {
        int best_val = s[i] - '0';
        int best_pos = i;

        // 在窗口内寻找能产生最大价值的来源
        for (int j = i; j < min(i + 10, n); ++j) {
            int current_val = (s[j] - '0') - (j - i);
            if (current_val > best_val) {
                best_val = current_val;
                best_pos = j;
            }
        }

        // 物理移动来源字符到当前位置i
        while (best_pos > i) {
            swap(s[best_pos], s[best_pos - 1]);
            best_pos--;
        }
        
        // 将当前位置i的字符值更新为计算出的最优值
        s[i] = (char)(best_val + '0');
    }
    cout << s << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            String s_input = sc.next();
            char[] s = s_input.toCharArray();
            int n = s.length;

            for (int i = 0; i < n; i++) {
                int best_val = s[i] - '0';
                int best_pos = i;

                // 在窗口内寻找能产生最大价值的来源
                for (int j = i; j < Math.min(i + 10, n); j++) {
                    int current_val = (s[j] - '0') - (j - i);
                    if (current_val > best_val) {
                        best_val = current_val;
                        best_pos = j;
                    }
                }

                // 物理移动来源字符到当前位置i
                int temp_pos = best_pos;
                while (temp_pos > i) {
                    char temp = s[temp_pos];
                    s[temp_pos] = s[temp_pos - 1];
                    s[temp_pos - 1] = temp;
                    temp_pos--;
                }
                
                // 将当前位置i的字符值更新为计算出的最优值
                s[i] = (char) (best_val + '0');
            }
            System.out.println(new String(s));
        }
    }
}

import sys

def solve():
    s = list(input())
    n = len(s)

    for i in range(n):
        best_val = int(s[i])
        best_pos = i

        # 在窗口内寻找能产生最大价值的来源
        for j in range(i, min(i + 10, n)):
            current_val = int(s[j]) - (j - i)
            if current_val > best_val:
                best_val = current_val
                best_pos = j
        
        # 物理移动来源字符到当前位置i
        # 使用 pop/insert 会导致 O(N^2) 超时，需要手动交换
        temp_pos = best_pos
        while temp_pos > i:
            s[temp_pos], s[temp_pos - 1] = s[temp_pos - 1], s[temp_pos]
            temp_pos -= 1
    
        # 将当前位置i的字符值更新为计算出的最优值
        s[i] = str(best_val)
    
    print("".join(s))


def main():
    t = int(input())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：贪心
时间复杂度：外层循环遍历字符串，复杂度为 $\mathcal{O}(N)$ 。内层循环在一个固定大小（最多10）的窗口内进行搜索，复杂度为 $\mathcal{O}(1)$ 。将字符移动到位的操作，最多也只移动10次。因此，总时间复杂度为 $\mathcal{O}(N)$ 。
空间复杂度：除了存储输入字符串外，我们只使用了常数个额外变量，因此空间复杂度为 $\mathcal{O}(N)$ 。