抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

从长度为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())
}

参考:

算法面试题,在数组中找出这样的数,它比它前面的数都大,比它后面的数都小

2018腾讯内部调岗面试试题3——找出数组中比左边大比右边的小的元素

算法: 在数组中找到左边数都比它小, 右边数都比它大的数


0条评论

发表评论