第二题写了个javascript的。不用编译可以直接Chrome/FF/IE js console里跑就好了。
思路是:先假定第一个元素就是pole,然后从位置1开始往后扫描。
如果后面的值都大于它,那正好,它就是了。
如果后面有值小于它,说明迄今为止的值都不可能为pole,下一个可能的pole是第一个
比迄今为止最大值还大(或相等)的值。
偷懒了一下假定原数组值都是正的。
function partition(a) {
if (!a || a.length == 0) return -1; // -1 means impossible, assume the
orignal array only contains positive values.
var possible = a[0];
var max = a[0];
for(var i = 1; i < a.length; i++){
if (possible >= 0) {
if (a[i] >= possible) {
max = a[i];
} else {
possible = -1;
}
} else {
if (a[i] >= max) {
possible = a[i];
max = a[i];
}
}
}
return possible;
}
// test cases
console.log(partition([])); // -1
console.log(partition([1])); // 1
console.log(partition([1,2,3])); // 1
console.log(partition([2,1,3])); // 3
console.log(partition([3,2,1])); // -1
console.log(partition([6,10,7,9,19,33])); // 6
console.log(partition([6,10,5,7,9,19,33,20])); // 19