题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
一个栈就是把队列反过来，那再来一个栈push进第一个栈就“正”过来了。
第一个栈就是存下反过来的序列。
每次push进一个数，要先判断stack2“正”序列是否为空，不为空要还原“反序列”，还要stack1 push进所有的stack2。
每次pop一个数，把stack1全部push进来，就变成了“正序列”，return stack2的pop即可。
但是想想，有个小优化，push的时候不用在stack1还原反序列，直接push进stack1，这样在pop的时候判断stack2是否为空，不为空，直接pop，这样把早先“入队列”的pop完，再push stack1的。加了一个判断，简化了第一个栈的操作。
任何时候pop要判断是否还有元素。
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack1.empty()&&stack2.empty()){
throw new RuntimeException("Queue is empty!");
}
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
import java.util.Stack;
class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
while(!stack2.empty()){
stack1.push(stack2.pop());
}
stack1.push(node);
}
public int pop() {
if(stack1.empty()&&stack2.empty()){
throw new RuntimeException("Queue is empty!");
}
while(!stack1.empty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
class Main {
}
然后又用我大JS做了一遍，我大JS，每个数组就是一个栈，233，直接push和pop方法。
注意js对pop() 时两个栈为空的处理。 js 是默认返回 undefined ，其他静态语言一般是报异常。
var stack1 = [],
stack2 = [];
function push(node) {
stack1.push(node);
}
function pop() {
if (!stack2.length&&!stack2.length) {
//处理
}
if (!stack2.length) {
while (stack1.length) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
/*
// 测试
var arr = [];
arr.push(1)
arr.push(2)
arr.push(3)
console.log(arr);
console.log(arr.pop());*/
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
普通查找时间复杂度为n，出在这里肯定是要找优化的。明显是二分，二分的条件，边界和判断就是关键。
序列保证是旋转过的，如果长度是2，直接返回右边的。我们现在就找这个边界值，未旋转的非递减序列左边肯定小于右边。现在我们就不断缩小这个边界存在的区间。
中间元素大于第一个元素，则这个中间元素处于从left开始到中间元素只有一个的序列当中，此时最小元素位于中间元素的后面。
中间元素小于第一个元素，则这个中间元素“非正常”，左面元素到这个元素之间包含了两个序列，最小的数肯定在中间元素前面。
我这个二分，是留存mid的，所以最后肯定是分到只剩下两个数，且这两个数一定是旋转的，那么右边就是最小的数。
eg：
3 1 2，返回3 1，因为缩小的是“旋转的区间的长度”
3 4 1，返回4 1，最终的都是右边最小，返回即可。
另外的最坏情况就是有相同的元素，array[l] == array[r] && array[l] == array[mid]，不能用条件来缩小查找区间，这时候的序列肯定只有两种数，只能顺序查找，找到第一个小的，直接break即可。
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int len = array.length;
if(len==0)
return 0;
int l = 0;
int r = len-1;
int mid = 0;
while(r-l!=1) {
mid = (l+r)/2;
if(array[l] == array[r] && array[l] == array[mid]){
return OtherSolve(array,l,r);
}
//当中间比第一个元素大时，最小数在右边，因为右边的最小序列整体都是小于左边的大序列
if(array[mid]>=array[l])
l = mid;
//当中间比第一个元素小时，最小数在左边，最小序列的任何一个数整体都是小于左边的大序列
else if(array[mid]<=array[l]) {
r = mid;
}
}
return array[r];
}
int OtherSolve(int array[],int l,int r){
int t = array[l];
for(int i = l+1; i<=r; i++) {
if(array[i]<t)
t = array[i];
}
return t;
}
}