class Solution {
public:
// 移除多余的空格，参照数组中移除元素，不要用erase本身O(n)时间复杂度外加for循环O(n^2)
void remove_extra_spaces(std::string& s){
int slow = 0, fast = 0;
for(;fast<s.size();fast++){
if (s[fast]!=' '){ // 遇到非空格才处理，删除所有空格
if (slow!=0) s[slow++] = ' '; //除了开头，非空格字符前添加空格
while(fast<s.size() && s[fast]!=' ') s[slow++] =s[fast++];// 添加非空格字符
}
}
s.resize(slow);// for循环最后slow++，slow就是新字符串长度
}
std::string reverseWords(std::string s) {
remove_extra_spaces(s);
std::reverse(s.begin(), s.end());
int start = 0;// 移动指向每个单词的首字符
for (int i=0; i<=s.size();i++){
if (i==s.size() || s[i]==' '){
// 迭代器右边界指向字符串最后字符的后一位 是s.begin()+i而不是s.begin()+i-1
std::reverse(s.begin()+start, s.begin()+i); // i指向每个单词后的空格
start = i+1;// 指向空格后下个单词的首字符
}
}
return s;
}
};