难度中等760
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"示例 2：
输入：s = " hello world "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。示例 3：
输入：s = "a good example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。提示：
1 <= s.length <= 104s包含英文大小写字母、数字和空格' 's中 至少存在一个 单词
**进阶：**如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
解题思路：双指针
这道题难的不是翻转，而是多出来的这些空格要我们如何去处理比较复杂！
如果这道题我们去控制每个单词间只有一个空格那么会比较复杂，所以我们简化一下，每次遇到空格，就进入循环，然后将空格全部删掉，接着手动为每个单词后面添加一个空格！
除此之外，我们在遍历这个字符串去除多余空格的时候，不能直接使用 erase 函数，因为这样子的话时间复杂度高达 O(n^2)，所以我们使用双指针，思路和去除数组中重复元素的题解是一样的！
使用双指针法来去移除空格，最后 resize（重新设置）一下字符串的大小，就可以做到O(n)的时间复杂度。
最后就是常规的翻转字符串，先翻转每个单词，再翻转整个字符串就能达到目的！
class Solution {
public:
string reverseWords(string s) {
// 利用双指针，去除所有的空格，时间复杂度为o(n)
int left = 0;
for(int i = 0; i < s.size(); ++i)
{
if(s[i] != ' ')
{
// 手动为每个单词间增加空格
if(left != 0)
s[left++] = ' ';
// 补上该单词，遇到空格说明单词结束
while(i < s.size() && s[i] != ' ')
s[left++] = s[i++];
}
}
s.resize(left); // 此时s的有效个数变为left大小，重置一下大小
// 翻转每个单词，最后翻转整个字符串
left = 0;
for(int i = 0; i < s.size(); ++i)
{
if(s[i] == ' ')
{
reverse(s.begin() + left, s.begin() + i);
left = i + 1;
}
}
reverse(s.begin() + left, s.end());
reverse(s.begin(), s.end());
return s;
}
};