本文共 5373 字，大约阅读时间需要 17 分钟。
为了根据给定的算法重新构造字符串，我们可以将字符串分为两轮，每轮包括两部分：选最小字符和选最大字符。每一步中，选择符合条件的字符并添加到结果字符串中，直到所有字符都被选完。
以下是实现该算法的代码：
import java.util.ArrayList;import java.util.List;public class SortString { public static String sortString(String s) { List chars = new ArrayList<>(); for (char c : s.toCharArray()) { chars.add(c); } StringBuilder result = new StringBuilder(); Character lastMinChar = null; Character lastMaxChar = null; while (!chars.isEmpty()) { // 选最小字符的部分 if (lastMinChar == null) { // 找到最小的字符 char minChar = Character.maxChar; for (char c : chars) { if (c < minChar) { minChar = c; } } if (minChar == Character.maxChar) { break; } for (int i = 0; i < chars.size(); i++) { if (chars.get(i) == minChar) { result.append(minChar); lastMinChar = minChar; chars.remove(i); // 检查是否有更大的字符 boolean hasLarger = false; for (char c : chars) { if (c > minChar) { hasLarger = true; break; } } if (!hasLarger) { break; } break; } } } else { // 找到比lastMinChar大的最小字符 char minChar = Character.maxChar; for (char c : chars) { if (c > lastMinChar && c < minChar) { minChar = c; } } if (minChar == Character.maxChar) { break; } for (int i = 0; i < chars.size(); i++) { if (chars.get(i) == minChar) { result.append(minChar); lastMinChar = minChar; chars.remove(i); // 检查是否有更大的字符 boolean hasLarger = false; for (char c : chars) { if (c > minChar) { hasLarger = true; break; } } if (!hasLarger) { break; } break; } } } // 处理选最大字符的部分 if (lastMaxChar == null) { // 找到最大的字符 char maxChar = Character.minChar; for (char c : chars) { if (c > maxChar) { maxChar = c; } } if (maxChar == Character.minChar) { break; } for (int i = 0; i < chars.size(); i++) { if (chars.get(i) == maxChar) { result.append(maxChar); lastMaxChar = maxChar; chars.remove(i); // 检查是否有更小的字符 boolean hasSmaller = false; for (char c : chars) { if (c < maxChar) { hasSmaller = true; break; } } if (!hasSmaller) { break; } break; } } } else { // 找到比lastMaxChar小的最大字符 char maxChar = Character.minChar; for (char c : chars) { if (c < lastMaxChar && c > maxChar) { maxChar = c; } } if (maxChar == Character.minChar) { break; } for (int i = 0; i < chars.size(); i++) { if (chars.get(i) == maxChar) { result.append(maxChar); lastMaxChar = maxChar; chars.remove(i); // 检查是否有更小的字符 boolean hasSmaller = false; for (char c : chars) { if (c < maxChar) { hasSmaller = true; break; } } if (!hasSmaller) { break; } break; } } } // 检查是否所有字符都被选完 if (chars.isEmpty()) { break; } } return result.toString(); }} 这个算法确保每一步都严格按照题目要求，先选最小字符，再选比上一个大的最小字符，然后选最大字符，再选比上一个小的最大字符，直到所有字符都被选完。
转载地址：http://ktmq.baihongyu.com/