最近遇到了一道很有趣的算法面试题，乍一看逻辑很简单，O(N^2)时间复杂度的解决方式可以在常规语义下得到解决。但是O(N^2)时间复杂度之下缓慢的运行效率和重复的计算总让人觉得还有可以优化的空间。接下来我们一起看一下这道题:

题目

  无序数组中找到左侧比他小右侧比他大的数
  eg: [1 3 2 4 5]
  result: [1 4 5] eg: [2 1 3 5 4]
  result: [3] eg: [5 4 6 2 8]
  result: [8] eg: [4 3 2 1]
  result: []

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

基本解法：扫描数组循环比较

常规思路是从左到右扫描数组，针对每个数，判断是否比左边的数都大，这是O(N)级别的操作，在为真的基础上继续判断是否比右边的数都小，这也是O(N)级别的操作，总时间复杂度就是O(N) * (O(N) + O(N)) = O(2N^2)，也就是O(N^2)级别的时间复杂度。这里我们就不给出代码了。

优化1: 正向扫描过程中记录最大值

我们可以看到每次比较当前数是否比所有前向数据都大的时候，可以记录当前已搜索序列中的最大值，正向扫描过程中只需要判断当前搜索值是否和大于该最大值即可，不需要进行O(N)级别的扫描。

如果扫描到的当前值大于等于已扫描的最大值，就进行一次向后的扫描，判断当前值是否是所有后向节点中的最小值，如果是的话，当前值就是我们寻找目标数组中的其中一个可行解。

具体代码如下：

/*
  方法一:
  空间复杂度O(1)， 时间复杂度O(N^2)
  对每一个元素，判断是否是当前最大元素，可以维护当前最大元素减少计算量 */
  public int[] calTargetMethod1(int[] arr) { int max = Integer.MIN_VALUE; int length = arr.length; ArrayList<Integer> resLst = new ArrayList<>(); for (int idx = 0; idx < length; idx++) { if (arr[idx] > max) { max = arr[idx]; if (allAbove(idx, arr)) { resLst.add(arr[idx]); } } } return getResult(resLst);
  } private boolean allAbove(int idx, int[] arr) { for (int i = idx + 1; i < arr.length; i++) { if (arr[i] < arr[idx]) { return false; } } return true;
  } private int[] getResult(ArrayList<Integer> resLst) { int[] res = new int[resLst.size()]; int idx = 0; for (int i : resLst) { res[idx] = i; idx++; } return res;
  }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
 

错误优化2: 排序后进行原位对比

如果保证全局唯一解的情况下，可以使用排序后原位对比的方式。因为可以知道的是在唯一解的情况下，小于目标值的数一定都出现在目标值左边，大于目标值的数一定会出现在目标值的右边。

比如：

testCase : [1, 3, 2, 4, 7, 6, 5]

排序后:

Sorted Array: [1, 2, 3, 4, 5, 6, 7]

进行按位对比就能找到唯一解: [4]。

但是如果在不保证唯一解或者不保证有解的情况下，比如:

testCase: [5, 4, 6, 2, 8]

排序后:

sorted Array:[2, 4, 5, 6, 8]

按照位对比寻找发现了两个疑似可行解:

Result:[4, 8]

但实际上[4]并不满足我们对于题目的需求，应当舍弃。

/*
  先排序，取对应位置，有bug */
  public int[] calTargetMethod2(int[] arr) { int[] sortArr = Arrays.copyOf(arr, arr.length); Arrays.sort(sortArr); ArrayList<Integer> resLst = new ArrayList<>(); for (int idx = 0; idx < arr.length; idx++) { if (arr[idx] == sortArr[idx]) { resLst.add(arr[idx]); } } return getResult(resLst);
  }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

由于用到了排序，这道题的最快时间效率是O(N * log (N))。

优化3: 双向扫描比较

在刚才的优化1中，我们通过记录正向扫描最大值的形式找到了所有满足大于等于前向节点的值，这时我们就要考虑，是否可以用空间换时间的方式，也可以通过后向扫描记录一些从后向前而看的最小值，然后寻找所有从前向后扫描过程中的最大值，和最后向前扫描过程中的最小值，都满足的所有值就是我们要寻找的解集合。

例如测试用例:

testCase: [1, 3, 2, 4, 5]

正向扫描，通过数组记录当前值是否是正向扫描过程中所有大于前向节点的值，得到数组：

forwardMarkArray: [1, 1, 0, 1, 1]

反向扫描，通过数组记录当前值是已经反向扫描过所有值中最小值的情况:

reverseArray: [1, 0 , 1, 1 ,1]

两数组相加:

sumArray:[2, 1, 1, 2, 2]

可以看到所有2对应的index就是我们要寻找的最终目标数组的坐标。

Result: [1, 4, 5]

具体代码如下：

/*
  时间复杂度O(N)，空间复杂度O(N)
  正向扫描数组，寻找满足大于所有前向节点的点并维护最大值，正向扫描数组标记该节点位置为1
  反向扫描数组，寻找满足小于所有后向节点的点并维护最小值，反向扫描数组标记该节点位置为1
  将正向反向数组求和，所有为2的idx对应的数组值即为所求 */
  public int[] calTargetMethod3(int[] arr) { int length = arr.length; int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; int[] forwardMarkArr = new int[length]; int[] reverseMarkArr = new int[length]; for (int i = 0; i < length; i++) { if (arr[i] > max) { forwardMarkArr[i]++; max = arr[i]; } } for (int i = length - 1; i >= 0; i--) { if (arr[i] < min) { reverseMarkArr[i]++; min = arr[i]; } } ArrayList<Integer> resLst = new ArrayList<>(); for (int i = 0; i < length; i++) { if (forwardMarkArr[i] + reverseMarkArr[i] == 2) { resLst.add(arr[i]); } } return getResult(resLst);
  }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
 

由于使用到了额外的记录数组，该算法的空间复杂度为O(N)，正反两次数组扫描以及求和数组的扫描，时间复杂度也是O(N)。

文章来源: zclhit.blog.csdn.net，作者：zclhit_，版权归原作者所有，如需转载，请联系作者。

原文链接：zclhit.blog.csdn.net/article/details/113725679