题目描述

求数组中比左边元素都大同时比右边元素都小的元素，返回这些元素的索引。要求时间复杂度$O(N)$

输入：[2, 3, 1, 8, 9, 20, 12]
输出：3, 4
解释：数组中 8, 9 满足题目要求，他们的索引分别是 3、4

解法

思路

最简单最暴力的就是没从头到尾遍历元素，对于每个元素分别往前、往后遍历一下，看看是否它是否满足条件。

这种解法的时间复杂度为$O(N^2)$，不符合题目要求。

通过分析可以得到，对于每个元素，如果它比左侧最大的值要大，同时比右侧最小的值要小，就满足条件。

那如果有这样两个数组，

left_max[i] 表示原数组 [0, i) 的最大值

right_min[i] 表示原数组 (i, n) 的最小值

内循环就可以通过 left_max[i] < nums[i] && nums[i] < right_min[i] 来判断了。

对于 left_max 和 right_min 这两数组，提前先算好，每个数组都能$O(N)$得到。

left_max 和 right_min 递推式如下：

left_max[i] = max(left_max[i-1], nums[i])

right_min[i] = min(right_min[i-1], nums[i])

总时间复杂度为 $O(N)$

代码

import ...

class Solution {
    public List<Integer> find(int[] nums) {
        int n = nums.length;
        int[] left_max = new int[n];
        int[] right_min = new int[n];
        Arrays.fill(left_max, Integer.MIN_VALUE);
        Arrays.fill(right_min, Integer.MAX_VALUE);

        for(int i = 1; i < n; i++) {
            left_max[i] = Math.max(left_max[i-1], nums[i-1]);
        }
        for(int i = n-2; i >= 0; i--) {
            right_min[i] = Math.min(right_min[i+1], nums[i+1]);
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 1; i < n-1; i++) {
            if(nums[i] > left_max[i] && nums[i] < right_min[i]) {
                res.add(i);
            }
        }
        return res;
    }
}

参考资料

1. 一道热乎的字节三面原创题