482，上升下降字符串

Original 山大王wld 数据结构和算法 2022-05-19

Freeing yourself up for something better in the future.

释放自己，为了更好的未来。

问题描述

给你一个字符串s，请你根据下面的算法重新构造字符串：

从s中选出最小的字符，将它接在结果字符串的后面。
从s剩余字符中选出最小的字符，且该字符比上一个添加的字符大，将它接在结果字符串后面。
重复步骤2，直到你没法从s中选择字符。
从s中选出最大的字符，将它接在结果字符串的后面。
从s剩余字符中选出最大的字符，且该字符比上一个添加的字符小，将它接在结果字符串后面。
重复步骤5，直到你没法从s中选择字符。
重复步骤1到6，直到s中所有字符都已经被选过。

在任何一步中，如果最小或者最大字符不止一个，你可以选择其中任意一个，并将其添加到结果字符串。

请你返回将s中字符重新排序后的结果字符串 。

示例 1：

输入：s = "aaaabbbbcccc"
输出："abccbaabccba"
解释：第一轮的步骤 1，2，3 后，结果字符串为 result = "abc"
第一轮的步骤 4，5，6 后，结果字符串为 result = "abccba"
第一轮结束，现在 s = "aabbcc" ，我们再次回到步骤 1
第二轮的步骤 1，2，3 后，结果字符串为 result = "abccbaabc"
第二轮的步骤 4，5，6 后，结果字符串为 result = "abccbaabccba"

示例 2：

输入：s = "rat"
输出："art"
解释：单词 "rat" 在上述算法重排序以后变成 "art"

示例 3：

输入：s = "leetcode"
输出："cdelotee"

示例 4：

输入：s = "ggggggg"
输出："ggggggg"

示例 5：

输入：s = "spo"
输出："ops"

提示：

1 <= s.length <= 500
s 只包含小写英文字母。

问题分析

这道题是让从字符串s中先选出升序的字符，然后再选出降序字符……一直这样循环，直到选完为止。因为题中的提示中说了s只包含小写英文字符，我们可以申请一个大小为26的数组，相当于26个桶。

把s中的每个字符分别放到对应的桶里，比如a放到第一个桶里，b放到第2个桶里……。
第1次从左往右遍历26个桶，从每个桶里拿出一个字符(如果没有就不用拿)
第2次从右往左遍历26个桶，从每个桶里拿出一个字符(如果没有就不用拿)
……
一直这样循环下去，直到所有的桶里的元素都拿完为止。

这里以示例为例，来画个图看下

原理比较简单，来看下代码

 1public String sortString(String s) {
 2    //相当于26个桶
 3    int[] bucket = new int[26];
 4    char[] charArr = s.toCharArray();
 5    //把s中的字符分别放到对应的桶里
 6    for (char c : charArr) {
 7        bucket[c - 'a']++;
 8    }
 9    //存储计算的结果
10    char[] res = new char[s.length()];
11    int index = 0;
12    while (index < s.length()) {
13        //先从左往右找，遍历26个桶,如果当前桶不为空，
14        //就从当前桶里拿出一个元素出来
15        for (int i = 0; i < 26; i++) {
16            if (bucket[i] != 0) {
17                res[index++] = (char) (i + 'a');
18                bucket[i]--;//拿出之后桶中元素的个数要减1
19            }
20        }
21        //从右往左拿，同上
22        for (int i = 25; i >= 0; i--) {
23            if (bucket[i] != 0) {
24                res[index++] = (char) (i + 'a');
25                bucket[i]--;
26            }
27        }
28    }
29    //把结果转化为字符串
30    return new String(res);
31}