从长度为n的数组中找出所有比左边大比右边的小的元素

以时间复杂度O(n)从长度为n的数组中找出同时满足下面两个条件的所有元素：
（1）该元素比放在它前面的所有元素都大；
（2）该元素比放在它后面的所有元素都小。
注意：左右两边第一个数不满足条件。

思路：

从右到左遍历构建一个最小值数组，只存放当前num[i]位置的最小值。
然后从左往右记录一个 lMax ，指存放当前遇到的最大值。
如果 lMax 比最小值数组中的值还要小，那么 lMax 则为大于前面所有元素且小于后面所有元素的值。

代码：

class FindPivotElements {

    fun solution(nums: IntArray) {
        val size = nums.size
        val rightMins = IntArray(size) { Int.MIN_VALUE }
        var rMin = nums[size - 1]
        //从右往左，寻找每个位置及其之后的最小数
        for (i in nums.indices.reversed()) {
            if (nums[i] < rMin) {
                rMin = nums[i]
            }
            rightMins[i] = rMin
        }
        var lMax = nums[0]
        //从左往右，寻找比左边大且比右边小的数
        for (i in 0 until nums.size - 1) {
            if (nums[i] > lMax) {
                lMax = nums[i]
                if (lMax < rightMins[i + 1]) {
                    println(nums[i])
                }
            }
        }
    }

}

测试代码：

fun main() {
    val nums = intArrayOf(1, 8, 6, 9, 10, 15, 12, 20)
    FindPivotElements().solution(nums)
}

输出：

9
10

另外的解法：栈

思路：

使用栈来存满足前面的值均小于当前值的值,用一个 max 来存到目前为止的最大值。
对于数组中的每个数 num , 先检查是否更小, 若当前值比栈中元素更小, 则之前压入栈中的值不再满足条件, 需出栈;
若当前值比目前的 max 更大, 则该值左边的数均小于它, 可以入栈。
最后留下来的就是需要的解.

fun solutionStack(nums: IntArray) {
    // 存储当前满足条件的值
    val stack = Stack<Int>()
    // 记录当前遍历过的最大值(新入栈的数必须不小于max)
    var max = nums[0]
    stack.push(nums[0])
    for (i in 0 until nums.size - 1) {
        // 先检查新值num是否小于栈内元素, 否则栈内元素不满足条件
        while (!stack.empty() && nums[i] <= stack.peek()) {
            stack.pop()
        }
        if (nums[i] > max) {
            stack.push(nums[i])
            max = nums[i]
        }
    }
    //输出结果
    println(stack.toString())
}