题目的主要信息：

• 将一个英文语句以单词为单位逆序排放
• 所有单词之间用一个空格隔开，没有仅含空格的案例
• 进阶要求：时间复杂度$O(n)O(n)$，空间复杂度$O(n)O(n)$

方法一：两次反转

具体做法：

将输入的字符串反转，得到了完全逆序的字符串，单词与单词之间确实是逆序了，但是单词内部也是逆序的，因此我们还要再遍历逆序后的字符串，以空格为界限，分割出单词，然后只对单词这部分进行反转，使之从逆序变成正序。

class Solution {
public:
    string ReverseSentence(string str) {
        int n = str.length();
        reverse(str.begin(), str.end()); //第一次整体反转
        for(int i = 0; i < n; i++){
            int j = i;
            while(j < n && str[j] != ' ') //以空格为界找到一个单词
                j++;
            reverse(str.begin() + i, str.begin() + j); //将这个单词反转
            i = j;
        }
        return str;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，$nn$为整个句子字符串的长度，遍历整个字符串和反转字符串都是$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，无额外空间

方法二：分割字符串+栈

具体做法：

我们都知道栈是先进后出的，于是我们可以用方法一中分割单词的方式，在大的句子字符串中分割出一个一个地单词，用substr函数。从头到尾遍历，将分割出来的单词送入栈中，然后按照栈中弹出的字符串顺序拼接单词即可使单词之间逆序。

class Solution {
public:
    string ReverseSentence(string str) {
        int n = str.length();
        stack<string> st;
        for(int i = 0; i < n; i++){ //遍历字符串，找到单词并入栈
            int j = i;
            while(j < n && str[j] != ' ')  //以空格为界，分割单词
                    j++;
                st.push(str.substr(i, j - i));  //单词进栈
                i = j;
        }
        str = "";
        while(!st.empty()){   //栈遵循先进后厨，单词顺序是反的
                str += st.top();
                st.pop();
                if(!st.empty())
                    str += " ";
        }
        return str;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，$nn$为整个句子字符串的长度，遍历整个字符串和弹出栈都是$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$，栈空最坏情况下长度为$nn$