一道关于数组的算法题

晚上从geeksforgeeks上看到一道算法题，题目如下：

Given an array, find an element before which all elements are smaller than it, and after which all are greater than it. Return index of the element if there is such an element, otherwise return -1.
Examples:

Input: arr[] = {5, 1, 4, 3, 6, 8, 10, 7, 9};
Output: Index of element is 4
All elements on left of arr[4] are smaller than it
and all elements on right are greater.

Input: arr[] = {5, 1, 4, 4};
Output: Index of element is -1

最暴力的方法枚举每个元素，将其与左右的元素进行比较，复杂度O(n^2)。这个时候按套路来的话就会发现这中间有很多重复性的工作。比如A[i]与A[0…i-1]比较之后，A[i+1]再与A[0…i]比较就没必要从A[0]开始了。只需要用一个元素记录A[i]左边最大的值。考虑到题目的意思，需要两个数组，一个保存左边部分的最大值，一个保存左边部分的最小值。

一个粗糙的C++版本就出来了。

int foo(vector<int>& nums) {
    int n = nums.size();
    vector<int> left(n), right(n);
    left[0] = INT_MIN;
    right[n-1] = INT_MAX;

    for(int i=1; i!=n; ++i) 
        left[i] = max(left[i-1], nums[i-1]);
    for(int i=n-2; i>=0; --i)
        right[i] = min(right[i+1], nums[i+1]);
    
    for(size_t i=0; i!=n; ++i) {
        if(nums[i]>left[i] && nums[i]<right[i])
        	return i;
    }
    return -1;
}

蛋疼的我又写了一个go语言版本的。

package main

import "fmt"

func foo(nums ...int) int {
    n := len(nums)
    left := make([]int, n)
    right := make([]int, n)
    left[0] = nums[0] - 1
    right[n-1] = nums[n-1] + 1
    
    for i := 1; i < n; i++ {
        if left[i-1] > nums[i-1] {
            left[i] = left[i-1]
        } else {
            left[i] = nums[i-1]
        }
    }
    
    for i := n - 2; i >= 0; i-- {
        if right[i+1] < nums[i+1] {
            right[i] = right[i+1]
        } else {
            right[i] = nums[i+1]
        }
    }
    
    ret := -1
    for i := 0; i < n; i++ {
        if left[i] < nums[i] && nums[i] < right[i] {
            ret = i
            break
        }
    }
    return ret
}

func main() {
    nums := []int{5, 1, 4, 3, 6, 8, 10, 7, 9}
    fmt.Println(foo(nums...))
}

然而仔细想一想第二个数组其实并没有必要，我们只需要用一个值保存最小值，并从右往左比较就可以了。代码很简单，就不写了。

然而有没有空间复杂度为O(1)的解法呢？一般面试的时候如果被这么问，答案肯定是有。怎么做呢？从左向右遍历，用一个值记录左边的最大值，如果遍历到某个元素大于其左边的最大值，可以将它作为一个candidate。继续像右遍历，同时检查此元素是否大于candidate，如果不大于，就把candidate废掉。那么需要几个变量呢？记录candidate的位置，candidate也可能不存在，所以需要一个flag，最后还需要一个值表示遍历过的元素的最大值。

int foo(vector<int>& nums) {
    bool exist = true;
    int candidate = 0, leftmax = nums[0];
    
    for(size_t i=1; i!=nums.size(); ++i) {
        leftmax = max(leftmax, nums[i-1]);
        if(exist == false && nums[i] > leftmax) {
            exist = true;
            candidate = i;
        }
        else if(exist == true && nums[i] <= nums[candidate]) {
            exist = false;
        }
    }
    
    return exist == true ? candidate : -1;
}