一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，其左边的数都小于等于它，右边的数都大于等于它。
第一个想法就是暴力。时间复杂度O(n^2)。
第二个想法：
利用一个辅助数组，记录每一个元素右侧的最小值是多少【这个元素是including的】。
遮掩，假设我们的数据是：
array[] = {7, 10, 2, 6, 19, 22, 32}，
那么
rightMin[] = {2, 2, 2, 6, 19, 22, 32}.
也就是说，32右侧的最小值是32，右侧的最小值是22,19右侧的最小指是19,6右侧的最小值是6,2右侧的最小值是2,10右侧的最小值是2,7右侧的最小值是2。
构建辅助数组的时间复杂度是o(n)的。
有了这个辅助数组之后，从头开始遍历数组，记录已经遍历过的数组的最大值max，
遇到数组当前值等于rightMin的值并且数组当前元素大于等于max，这个值就是一个所求的数组值。输出它。然后继续遍历数组【因为要求是求出所有这样的元素】。
看代码：
package a;
public class CopyOfTest1 {
public static void main(String s[]) {
func(new int[] { 7, 10, 2, 6, 19, 22, 32 });
}
public static void func(int[] d) {
int[] ds = new int[d.length];
for (int i = ds.length - 1; i >= 0; i--) {
if (i == ds.length - 1) {
ds[i] = d[i];
} else {
if (d[i] < ds[i + 1]) {
ds[i] = d[i];
} else {
ds[i] = ds[i + 1];
}
}
}
for (int i = 0; i < ds.length; i++) {
System.out.print(ds[i] + "\t");
}
System.out.println();
for (int i = 0; i < ds.length; i++) {
System.out.print(d[i] + "\t");
}
System.out.println();
int max = -10000;
for (int i = 0; i < ds.length; i++) {
if (max < d[i]) {
max = d[i];// 更新最大值
}
if (ds[i] == d[i] && max <= d[i]) {
System.out.println(ds[i]);
}
}
}
}
算法时间复杂度为O(n)，空间复杂度为O(n)。空间换时间思想。