題目

Given an array A, partition it into two (contiguous) subarrays left and right so that:

• Every element in left is less than or equal to every element in right.left and right are non-empty.left has the smallest possible size.
• Return the length of left after such a partitioning. It is guaranteed that such a partitioning exists.

思路

左側的最大值比右側所有的值小。遍歷數(shù)組，記錄左側最大值，當遍歷到的值比左側最大值大是，則該值加入左側數(shù)組，并且更新左側最大值；當遍歷到的值比左側最大值大時，更新當前最大值。

代碼

func partitionDisjoint(A []int) int {

    leftbigest := A[0]
    curBigest := leftbigest
    leftLong := 1
    for i:=1 ; i < len(A) ; i ++ {
        if (A[i] < leftbigest) {
            leftbigest = curBigest
            leftLong = i+1
        } else if(A[i] > curBigest){
            curBigest = A[i]
        }
    }
    return leftLong
}