栈和队列
2020-02-08 本文已影响0人
isuntong
- 滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
暴力：
public ArrayList<Integer> maxInWindows1(int [] num, int size) {
ArrayList<Integer> res = new ArrayList<>();
if (num == null || size <= 0 || num.length < size) {
return res;
}
// 暴力破解法
int len = num.length;
int maxIdx = len - size;
for (int i=0; i<= maxIdx; i++) {
// 获取当前序列的最大值
int curMax = num[i];
for (int j=i+1; j<i+size; j++) {
curMax = curMax > num[j] ? curMax : num[j];
}
// 最大值加入res
res.add(curMax);
}
return res;
}
双端队列法：
public static ArrayList<Integer> maxInWindows2(int[] num, int size) {
ArrayList<Integer> maxWindows = new ArrayList<>();
if (num == null || size == 0 || num.length == 0 || num.length < size)
return maxWindows;
Deque<Integer> dq = new LinkedList<>();
for (int i = 0; i < size; i++) {
// 如果已有数字小于待存入的数据，
// 这些数字已经不可能是滑动窗口的最大值
// 因此它们将会依次地从队尾删除
while (!dq.isEmpty() && num[i] > num[dq.getLast()])
dq.removeLast();
dq.addLast(i);
}
//System.out.println(dq);
for (int i = size; i < num.length; i++) {
maxWindows.add(num[dq.getFirst()]);
while (!dq.isEmpty() && num[i] >= num[dq.getLast()])
dq.removeLast();
if (!dq.isEmpty() && dq.getFirst() <= i - size)
dq.removeFirst();
dq.addLast(i);
}
maxWindows.add(num[dq.getFirst()]);
return maxWindows;
}
- 用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
while(!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
stack1.push(node);
}
public int pop() {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
只是考虑栈和队列的特点
- 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
/*
* 思路：用一个栈stack保存数据，用另外一个栈min保存依次入栈最小的数
* 比如，stack中依次入栈，5, 4, 3, 8, 10,11,12,1
* 则min依次入栈，5, 4, 3, 3, 3, 3, 3, 1
* 每次入栈的时候，如果入栈的元素比min中的栈顶元素小或等于则入栈，否则入stack的栈顶元素。
* 保持stack中和min中保持相同个数的元素 ，同时保持min的栈顶是此时原栈的最小值。
*/
Stack<Integer> stackData = new Stack<>(); //声明时候的异同
Stack<Integer> stackMin = new Stack<Integer>();
public void push(int node) {
stackData.push(node);
// 如果min为空或者node比min栈中的元素小，则入min栈
if(stackMin.size() == 0 || stackMin.peek() > node)
stackMin.push(node);
else // 否则把min栈中的顶部元素重复入栈
stackMin.push(stackMin.peek());
}
public void pop() {//因为时刻保持两个栈的高度相同，所以两个都pop，时刻保持min的栈顶是原栈的最小值。
//如果返回应该是返回原栈的。
if(!stackData.isEmpty()){
stackData.pop();
stackMin.pop();
}
}
public int top() {
return stackData.peek();
}
public int min() {
return stackMin.peek();
}
- 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
/**借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，
然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，
直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，
这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。
举例：
入栈1,2,3,4,5
出栈4,5,3,2,1
首先1入辅助栈，此时栈顶1≠4，继续入栈2
此时栈顶2≠4，继续入栈3
此时栈顶3≠4，继续入栈4
此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3
此时栈顶3≠5，继续入栈5
此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3
….
依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。
* @param pushA
* @param popA
* @return
*/
public boolean IsPopOrder(int[] pushA, int[] popA) {
if (pushA == null || popA == null || pushA.length == 0
|| popA.length == 0)
return false;
int index = 0; //作为弹出序列的一个索引
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < pushA.length; i++) {
stack.push(pushA[i]);
while (!stack.isEmpty() && stack.peek() == popA[index]) {// 当栈不为空且栈顶元
//素等于弹出序列元素时候，就弹出一个，同时让弹出序列后移一个
stack.pop();
index++;
}
}
return stack.isEmpty();//如果最后，栈不为空，相当于没有按照给定的弹出popA弹出完毕，
//就说明不能按照popA，返回false
}
