186. 反转字符串中的单词 II

给你一个字符数组 s ，反转其中 单词 的顺序。

单词 的定义为：单词是一个由非空格字符组成的序列。s 中的单词将会由单个空格分隔。

必须设计并实现 原地 解法来解决此问题，即不分配额外的空间。

示例 1：

输入：s = ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
输出：["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

示例 2：

输入：s = ["a"]
输出：["a"]

提示：

• 1 <= s.length <= 10^5
• s[i] 可以是一个英文字母（大写或小写）、数字、或是空格 ' ' 。
• s 中至少存在一个单词
• s 不含前导或尾随空格
• 题目数据保证：s 中的每个单词都由单个空格分隔

双指针-反转整个字符串+反转每个单词

先整体反转，再局部反转

class Solution {
    // 反转字符串中的单词
    public void reverseWords(char[] s) {
        reverseCharacters(s); // 先整体反转字符串
        reverseEachWord(s); // 再反转每个单词
    }

    // 反转字符串中的字符
    public void reverseCharacters(char[] s) {
        reverseCharacters(s, 0, s.length - 1); // 调用重载方法
    }

    // 反转字符串中每个单词
    public void reverseEachWord(char[] s) {
        int length = s.length;
        int begin = -1, end = -1; // 记录当前单词的起始和结束位置
        
        // 正序遍历
        for (int i = 0; i < length; i++) {
            char c = s[i];
            if (c == ' ') { // 如果当前字符为空格
                reverseCharacters(s, begin, end); // 反转当前单词
                begin = i + 1; // 更新下一个单词的起始位置
                end = i + 1; // 更新下一个单词的结束位置
            } else { // 如果当前字符不为空格
                if (begin < 0) { // 如果尚未记录当前单词的起始位置
                    begin = i; // 记录当前单词的起始位置
                }
                end = i; // 更新当前单词的结束位置
            }
        }
        
        reverseCharacters(s, begin, end); // 反转最后一个单词。重点。
    }

    // 反转字符串中指定范围内的字符
    public void reverseCharacters(char[] s, int low, int high) {
        while (low < high) {
            char c1 = s[low], c2 = s[high]; // 获取要交换的字符
            s[low] = c2; // 将后一个字符放到前一个字符的位置
            s[high] = c1; // 将前一个字符放到后一个字符的位置
            
            low++; // 前指针向后移动
            high--; // 后指针向前移动
        }
    }
}

时间复杂度O(n)，空间复杂度O(1)