⭐ 题目日期：

字节 - 2024/9/23

🧗难度系数：

⭐️ ⭐️ ⭐ ⭐

📝思路分析：

对于每个元素 nums[i]，需要知道它左侧所有元素的最小值，以及右侧所有元素的最大值。暴力解法显然时间复杂度过高O(n^2)，如何优化？遍历数组时，我们可以记录遍历到当前元素 i 为止的最小值（[1, i]）以及最大值([i, n - 1])。然后再扫描一遍记录的最大最小值与数组的值进行比较，从而找到满足题目要求的数。

💻代码：

Java

public List<Integer> findTarget(int[] nums) {
 List<Integer> result = new ArrayList<>();
      if (nums == null || nums.length < 3) {
     return result;
 }
      int n = nums.length;
 int[] left = new int[n];
 int[] right = new int[n];

 left[0] = nums[0];
 right[n - 1] = nums[n - 1];

 for (int i = 1; i < n - 1; i++) {
     left[i] = Math.min(left[i - 1], nums[i]);
     int rightIndex = n - 1 - i;
     right[rightIndex] = Math.max(right[rightIndex + 1], nums[rightIndex]);
 }

 for (int i = 1; i < n - 1; i++) {
     if (nums[i] < left[i - 1] && nums[i] > right[i + 1]) {
         result.add(nums[i]);
     }
 }

 return result;
}

🚵🏻复杂度分析：

时间复杂度：O(n), n 为数组的长度，线性扫描数组两遍 O(2n) --> O(n) 空间复杂度：O(n), 存储左边的最小值数组 O(n), 存储右边最大值 O(n), O(2n) --> O(n)