>[success] # Leetcode -- 1370上升下降字符串 * 题目描述 给你一个字符串 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 只包含小写英文字母。 ~~~ 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/increasing-decreasing-string 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 >[danger] ##### 简单概括 先将字符串中不重复的每一项**先升序排列**在**降序排列依**次交替组成新字符串 >[info] ## 题解 题目中提到字符串是由**小写字母**组成，因此可以利用**ascii** 映射数组脚标思路来做字母存储，因为在数组中存储后，每个字母此时已经是按照升序排序好，因此只要**正序倒序** 反复从数组取值即可   >[danger] ##### js 解题 ~~~ var sortString = function (s) { // 将字符串根据ascii 映射放入对应数组脚标中 const array = new Array(26).fill(0) const ascii_a = 'a'.charCodeAt(0) for (let char of s) { // 转换ascii 码 const idx = char.charCodeAt(0) array[idx - ascii_a]++ } // 按升降序依次正反数组取值 let str = '' // 一直循环直到 新生成的字符串长度等于原来字符串长度 while (str.length < s.length) { // 升序排列 for (let i = 0; i < 26; i++) { if (array[i]) { str += String.fromCharCode(i + ascii_a) array[i]-- } } // 降序排列 for (let i = 25; i >= 0; i--) { if (array[i]) { str += String.fromCharCode(i + ascii_a) array[i]-- } } } return str } ~~~ >[danger] ##### java 解题 ~~~ public class Solution { public String sortString(String s) { // 创建一个26长度数组 byte[] asciiLs = new byte[26]; char asciiLs_a = 'a'; // 将字符依次保存 for(int c:s.toCharArray()){ int idx = c-asciiLs_a; asciiLs[idx]++; } // 记录新的字符串 这种拼接比较慢可以使用数组List ans = new ArrayList<>(); String res = ""; while(res.length()<s.length()){ // 升序记录 for(int i=0;i<26;i++){ if(asciiLs[i]!=0){ // 找到就去掉一次 asciiLs[i]--; res+=String.valueOf((char)(i+asciiLs_a)); } } // 降序 for(int i=25;i>=0;i--){ if(asciiLs[i]!=0){ // 找到就去掉一次 asciiLs[i]--; res+=String.valueOf((char)(i+asciiLs_a)); } } } return res; } } ~~~ >[info] ## 看到一个扩展思路 直接` while (--end >= 0)` 这种将计算放到**while** 条件中 ~~~ /** * @param {string} s * @return {string} */ var sortString = function(s) { // 计数法 // a-z => 97-122 // index是字母-97，值是出现的次数 let arr = Array(26).fill(0) const base = 'a'.charCodeAt() for (const char of s) { // 0-25 arr[char.charCodeAt() - base] ++ } let ans = '' while (ans.length < s.length) { let = start = -1, end = 26 while (++start < 26) { if (arr[start] !== 0) { ans += String.fromCharCode(start + base) arr[start] -- } } while (--end >= 0) { if (arr[end] !== 0) { ans += String.fromCharCode(end + base) arr[end] -- } } } return ans; }; ~~~