题目
描述
实现一个带有取最小值min方法的栈,min方法将返回当前栈中的最小值。
你实现的栈将支持push
,pop
和 min
操作,所有操作要求都在O(1)时间内完成。
样例
如下操作:push(1)
,pop()
,push(2)
,push(3)
,min()
, push(1)
,min()
返回 1,2,1
解答
思路
建立两个栈,一个保持顶端是最小的数,另一个保存剩下的数据。
代码
public class Solution {
/**
* param A : an integer sorted array
* param target : an integer to be inserted
* return : an integer
*/
public int searchInsert(int[] A, int target) {
// write your code here
int low = 0, high = A.length - 1, mid = 0;
if(A.length == 0) return 0;
while(low <= high){
mid = (low + high) / 2;
if(A[mid] == target) return mid;
else if(A[mid] > target) high = mid-1;
else low = mid+1;
}
if(A[mid] > target) return mid;
else return mid + 1;
}
}