博客

题目描述

求数组中比左边元素都大同时比右边元素都小的元素，返回这些元素的索引。

要求时间复杂度 O(N)。

输入：[2, 3, 1, 8, 9, 20, 12]

输出：3, 4

解释：数组中 8, 9 满足题目要求，他们的索引分别是 3、4

方法一：

最简单的思路是遍历数组，对于每个元素分别往前、往后遍历一下，看看是否它是否满足条件。

for(int i = 0; i < n; i ++) {
  for(int j = 0; j < i; j ++) {
    //左侧是否都比它小
  }
  for(int k = j + 1; k < n; k ++) {
    //右侧是否都比它大
  }
  //若两条件均满足则记录下来
}

import java.util.*;

public class Main_findKGreatLeftLessRight {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 暴力求解
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 元素个数
		int[] nums = new int[n];
		for(int i = 0; i &l