C++刷leetcode（1370. 上升下降字符串）【数据结构】

糖逗

题目描述：

1. 给你一个字符串 s ，请你根据下面的算法重新构造字符串：
   
2. 
   
3. 从 s 中选出 最小 的字符，将它 接在 结果字符串的后面。
   
4. 从 s 剩余字符中选出 最小 的字符，且该字符比上一个添加的字符大，将它 接在 结果字符串后面。
   
5. 重复步骤 2 ，直到你没法从 s 中选择字符。
   
6. 从 s 中选出 最大 的字符，将它 接在 结果字符串的后面。
   
7. 从 s 剩余字符中选出 最大 的字符，且该字符比上一个添加的字符小，将它 接在 结果字符串后面。
   
8. 重复步骤 5 ，直到你没法从 s 中选择字符。
   
9. 重复步骤 1 到 6 ，直到 s 中所有字符都已经被选过。
   
10. 在任何一步中，如果最小或者最大字符不止一个 ，你可以选择其中任意一个，并将其添加到结果字符串。
    
11. 
    
12. 请你返回将 s 中字符重新排序后的 结果字符串 。
    
13. 
    
14.  
    
15. 
    
16. 示例 1：
    
17. 
    
18. 输入：s = "aaaabbbbcccc"
    
19. 输出："abccbaabccba"
    
20. 解释：第一轮的步骤 1，2，3 后，结果字符串为 result = "abc"
    
21. 第一轮的步骤 4，5，6 后，结果字符串为 result = "abccba"
    
22. 第一轮结束，现在 s = "aabbcc" ，我们再次回到步骤 1
    
23. 第二轮的步骤 1，2，3 后，结果字符串为 result = "abccbaabc"
    
24. 第二轮的步骤 4，5，6 后，结果字符串为 result = "abccbaabccba"
    
25. 示例 2：
    
26. 
    
27. 输入：s = "rat"
    
28. 输出："art"
    
29. 解释：单词 "rat" 在上述算法重排序以后变成 "art"
    
30. 示例 3：
    
31. 
    
32. 输入：s = "leetcode"
    
33. 输出："cdelotee"
    
34. 示例 4：
    
35. 
    
36. 输入：s = "ggggggg"
    
37. 输出："ggggggg"
    
38. 示例 5：
    
39. 
    
40. 输入：s = "spo"
    
41. 输出："ops"
    
42.  
    
43. 
    
44. 提示：
    
45. 
    
46. 1 <= s.length <= 500
    
47. s&#160;只包含小写英文字母。
    
48. 
    
49. 来源：力扣（LeetCode）
    
50. 链接：https://leetcode-cn.com/problems/increasing-decreasing-string
    
51. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     string sortString(string s) {
   
4.         string res;
   
5.         map<char, int> store;
   
6.         for(auto cha : s)store[cha]++;
   
7.         while(res.size() != s.size()){
   
8.             char temp = 'a' - 1;
   
9.             string temp1 = s;
   
10.             sort(temp1.begin(), temp1.end());
    
11.             for(int i = 0; i < s.size(); i++){
    
12.                 if(temp1[i] > temp && store[temp1[i]] !=0){
    
13.                     res.push_back(temp1[i]);
    
14.                     temp = temp1[i];
    
15.                     store[temp1[i]]--;
    
16.                 }
    
17.                 if(res.size() == s.size()) return res;
    
18.             }
    
19.             temp = 'z' + 1;
    
20.             sort(temp1.begin(), temp1.end(), [](char&a, char&b){return a > b;});
    
21.             for(int i = 0; i < s.size(); i++){
    
22.                 if(temp1[i] < temp&&store[temp1[i]] !=0){
    
23.                     res.push_back(temp1[i]);
    
24.                     temp = temp1[i];
    
25.                     store[temp1[i]]--;
    
26.                 }
    
27.                 if(res.size() == s.size()) return res;
    
28.             }
    
29.         }
    
30.         return res;
    
31.     }
    
32. };

复制代码

注意事项：
1.循环的中间判断。
2.map的建立防止多次访问超过某一字符串的最大个数。