http://blog.csdn.net/beiyeqingteng/article/details/7167823

這個博客不錯，要關注下~

問題：

一個int數組, 比如 array[]，里面數據無任何限制，要求求出所有這樣的數array[i]，其左邊的數都小于等于它，右邊的數都大于等于它。能否只用一個額外數組和少量其它空間實現。

分析：

最原始的方法是檢查每一個數 array[i] ，看是否左邊的數都小于等于它，右邊的數都大于等于它。這樣做的話，要找出所有這樣的數，時間復雜度為O(N^2)。

其實可以有更簡單的方法，我們使用額外數組，比如rightMin[]，來幫我們記錄原始數組array[i]右邊（包括自己）的最小值。假如原始數組為： array[] = {7, 10, 2, 6, 19, 22, 32}， 那么rightMin[] = {2, 2, 2, 6, 19, 22, 32}. 也就是說，7右邊的最小值為2, 2右邊的最小值也是2。

有了這樣一個額外數組，當我們從頭開始遍歷原始數組時，我們保存一個當前最大值 max， 如果當前最大值剛好等于rightMin[i]， 那么這個最大值一定滿足條件。還是剛才的例子。

第一個值是7，最大值也是7，因為7 不等于 2， 繼續，

第二個值是10，最大值變成了10，但是10也不等于2，繼續，

第三個值是2，最大值是10，但是10也不等于2，繼續，

第四個值是6，最大值是10，但是10不等于6，繼續，

第五個值是19，最大值變成了19，而且19也等于當前rightMin[4] = 19, 所以，滿足條件。

如此繼續下去，后面的幾個都滿足。

設array[i]是滿足條件的數，則從0-i的最大得數是array[i], 從i-n-1最小的數是array[i]，所有要找一個最大值等于最小值的數

/*** @author beiyeqingteng* @link http://blog.csdn.net/beiyeqingteng*/ public static void smallLarge(int[] array) throws Exception{//the array's size must be larger than 2if (array == null || array.length < 1) {throw new Exception("the array is null or the array has no element!");}int[] rightMin = new int[array.length];rightMin[array.length - 1] = array[array.length - 1];//get the minimum value of the array[] from i to array.length - 1for (int i = array.length - 2; i >= 0; i--) {if (array[i] < rightMin[i + 1]) {rightMin[i] = array[i];} else {rightMin[i] = rightMin[i + 1];}}int leftMax = Integer.MIN_VALUE;for (int i = 0; i < array.length; i++) {if (leftMax <= array[i]) {leftMax = array[i];if (leftMax == rightMin[i]) {System.out.println(leftMax);}}} }

總結

以上是生活随笔為你收集整理的在数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。