库函数

思路

1. 使用 split() 方法按照空格分割，得数组 arr
2. 逆序遍历 arr，并添加到 res 中

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] arr = in.nextLine().split(" ");
        StringBuilder res = new StringBuilder();
        for (int i = arr.length - 1; i >= 0; i--) {
            res.append(arr[i]);
            res.append(" ");
        }
        System.out.println(res);
        in.close();
    }
}

• 时间复杂度：$O(n)O(n)$
• 空间复杂度：$O(n)O(n)$

双指针

由于 Java 中 String 是不可变的，所以无法像 C++ 中做到空间 $O(1)O(1)$。但是，如果所给输入为 char[] 数组，则可以做到“原地算法”，将空间降为 $O(1)O(1)$ （这里假装输入是 char[] :smile:）

思路

• reverse(char[] arr, int left, int right) 函数：双指针反转 数组区间 arr[left, right] （左闭右闭区间）
• 反转每一个单词（空格分隔）
  • [I am a boy] --> [I ma a yob]
• 整体反转全部 arr
  • [I ma a yob] --> [boy a am I]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char[] arr = s.toCharArray();
        int n = arr.length;
        int left = 0;
        // 反转每一个单词
        while (left < n) {
            int right = left;
            while (right + 1 < n && arr[right + 1] != ' ') {
                right++;
            }
            reverse(arr, left, right);
            // arr[right]是当前单词的末尾，arr[right + 1]为空格，arr[right + 2]为下一个单词开头（或越界）
            left = right + 2;
        }
        // 整体反转
        reverse(arr, 0, n - 1);
        System.out.println(new String(arr));
        in.close();
    }
    
    // 双指针反转, arr[left, right]
    static void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}