第一章：栈与队列
第一章：栈与队列
设计一个有getMin功能的栈
要求：pop，push，getMin的时间复杂度为：O(1)
public class stackTemplate {
// 记录插入值
private Stack<Integer> stack = new Stack<>();
// 记录插入值的最小值
private Stack<Integer> minStack = new Stack<>();
public void push(int value) {
stack.push(value);
// 如果最小值栈的栈顶元素 大于 当前元素，则说明有新的最小值了，
if (minStack.isEmpty() || minStack.peek() >= value) {
minStack.push(value);
}
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
Integer pop = stack.pop();
if (pop <= minStack.peek()) {
minStack.pop();
}
return pop;
}
public int getMin() {
return minStack.peek();
}
public boolean isEmpty() {
return stack.isEmpty();
}
}由两个栈组成的队列
public class myQueue {
private Stack<Integer> inStack = new Stack<>();
private Stack<Integer> outStack = new Stack<>();
public boolean isEmpty() {
return inStack.isEmpty() && outStack.isEmpty();
}
public void push(int value) {
inStack.push(value);
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("栈为空");
}
pushToPop();
return outStack.pop();
}
public int peek() {
if (isEmpty()) {
throw new RuntimeException();
}
pushToPop();
return outStack.peek();
}
private void pushToPop() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
}如何仅用递归函数和栈操作逆序一个栈
通过递归函数实现栈中元素的逆序，比如放入：1,2,3,4. 逆序后：4,3,2,1
// 递归逆序栈 其实底层利用了栈帧的局部变量表去存储临时变量
// 1. 每次pop()，返回栈底元素
public int getAndRemoveLastElement(Stack<Integer> stack) {
Integer pop = stack.pop();
if (stack.isEmpty()) {
return pop;
}
int lastElement = getAndRemoveLastElement(stack);
stack.push(pop);
return lastElement;
}
// 2. 逆序栈
public void reverse(Stack<Integer> stack) {
// 如果为空，说明已经到底了，栈内没元素了
if (stack.isEmpty()) {
return;
}
// 我们可以理解为，每次我就去取栈底的值，
int element = getAndRemoveLastElement(stack);
// 剩下的每一次递归都会去取栈底元素，直到为空
reverse(stack);
// 将栈底元素放到栈顶
stack.push(element);
}用一个栈实现另一个栈的排序
方法1（利用栈帧）
Stack<Integer> helpStack = new Stack<>();
public void reverse(int value) {
if (helpStack.isEmpty() || helpStack.peek() >= value) {
helpStack.push(value);
return;
}
Integer pop = helpStack.pop();
reverse(value);
helpStack.push(pop);
}
public void reverseByStack(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
// 将stack内所有元素有序放入helpStack，所有元素访问后，helpStack有序，则导入stack，保证stack有序
while (!stack.isEmpty()) {
reverse(stack.pop());
}
while (!helpStack.isEmpty()) {
stack.push(helpStack.pop());
}
}方法2（利用栈本身，更省空间）
// 通过一个栈来帮另一个栈做排序， 将多余的值直接放入stack，性能更好，也更节省空间
public void reverseByStackPlus(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
Stack<Integer> helpStack = new Stack<>();
while (!stack.isEmpty()) {
Integer cur = stack.pop();
while (!helpStack.isEmpty() && helpStack.peek() < cur) {
stack.push(helpStack.pop());
}
helpStack.push(cur);
}
while (!helpStack.isEmpty()) {
stack.push(helpStack.pop());
}
}生成窗口最大值数组(双端队列)
输入：整形数组arr，窗口大小w。
输出：一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下最大值
/**
* 生窗口最大值数组，本题的关键在于利用双端队列，来记录滑动窗口的最大值
* 为啥用双端队列？ 因为我们需要动态的从队列的头和尾更新值
* @param arr 输入数组
* @param w 窗口大小
*/
public static int[] getMaxWindow(int[] arr, int w) {
if (arr == null || arr.length < w || w<1) {
return null;
}
// arr.length - w + 1 表示窗口大小w时，最终能获取到多少个最大值
int[] res = new int[arr.length - w + 1];
int index = 0;
// 双端队列，记录窗口内最大值，并进行数据的更新，
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < arr.length; i++) {
// 插入策略
while (!queue.isEmpty() && arr[queue.peekLast()] <= arr[i]) {
// 队列中记录的是最大值的下标，方便更新时，判断是否过期
queue.pollLast();
}
queue.addLast(i);
// 弹出策略 i-w 表示过期值，比如i=5，w=3,i-w=2, 当前遍历到i=5的点，窗口长度为3，那当前窗口内有效值应该是{3,4,5}，2已经过期了
if (queue.peekFirst() == i-w) {
queue.pollFirst();
}
if (i >= w -1) {
res[index++] = arr[queue.peekFirst()];
}
}
return res;
}单调栈结构
给定一个不含有重复值的数组arr，找到每个i位置左边和右边离i位置最近且值比arr[i]小的位置，返回所有位置的相应信息
/**
* 单调栈结构-找到每个节点离自己最近且比自己小的节点位置
* 这里默认arr内无重复值
*/
public static int[][] rightWay(int[] arr) {
int[][] res = new int[arr.length][2];
// 栈内存储节点位置
Stack<Integer> stack = new Stack<>();
// 策略：遍历数组，并将值放入栈中，
// 如果比栈顶值大，则直接放入，下面的值就是离自己最近的最小值点
// 如果比栈顶值小，则将栈中比自己大的都弹出，确认对应的坐标
for (int i = 0; i < arr.length; i++) {
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
Integer popIndex = stack.pop();
res[popIndex][0] = stack.isEmpty()?-1:stack.peek();
res[popIndex][1] = i;
}
stack.push(i);
}
// 最后如果栈中还有数据，则一定是升序，也就是说栈内的每个节点都是左边有比自己小的，右边没有。
// 这里需要注意栈底的点，这个点是左边也没有，右边也没有
while (!stack.isEmpty()) {
Integer popIndex = stack.pop();
res[popIndex][0] = stack.isEmpty()?-1:stack.peek();
res[popIndex][1] = -1;
}
return res;
}/**
* 单调栈结构-找到每个节点离自己最近且比自己小的节点位置
* 这里默认数组内有重复值
*/
public static int[][] rightWay(int[] arr) {
int[][] res = new int[arr.length][2];
// 栈内存储节点位置，节点用List，来存储多个相同的值，List内部存储的也是坐标
Stack<List<Integer>> stack = new Stack<>();
// 策略：遍历数组，并将值放入栈中
// 如果比栈顶值大，则直接放入，下面的值就是离自己最近的最小值点
// 如果和栈顶值一样，则加入栈顶的元素集合中
// 如果比栈顶值小，则将栈中比自己大的都弹出，确认对应的坐标
for (int i = 0; i < arr.length; i++) {
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
List<Integer> popList = stack.pop();
int leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popi : popList) {
res[popi][0] = leftIndex;
res[popi][1] = i;
}
}
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(i);
} else {
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
while (!stack.isEmpty()) {
List<Integer> popList = stack.pop();
int leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer popi : popList) {
res[popi][0] = leftIndex;
res[popi][1] = -1;
}
}
return res;
}求最大子矩阵的大小（单调栈应用）
/**
* 求最大子矩阵的大小 -》 单调栈
* @param arr
* @return
*/
public static int maxRecSize(int[][] arr) {
Stack<Integer> stack = new Stack<>();
// 记录切分后每个位置的高度
int[] record = new int[arr[0].length];
int max = 0;
// 步骤1：将二维数组切割为一维数组，record[i] 表示i位置上有多高
for (int[] curList : arr) {
for (int i = 0; i < curList.length; i++) {
record[i] += curList[i];
}
}
// 步骤2：利用单调栈找出每个点左右两侧，离自己最近且比自己小的
for (int i = 0; i < record.length; i++) {
while (!stack.isEmpty() && record[i] < record[stack.peek()]) {
// 如果当前值小于栈顶元素，说明栈顶元素列的最大面积已经能计算出来了
int popIndex = stack.pop();
int popLeftIndex = stack.isEmpty() ? -1 : stack.peek();
// 面积值:(i-popLeftIndex-1)*record[popIndex]
max = Math.max(max, (i - popLeftIndex - 1) * record[popIndex]);
}
stack.push(i);
}
// 栈内可能还有剩余元素
while (!stack.isEmpty()) {
int popIndex = stack.pop();
int popLeftIndex = stack.isEmpty() ? -1 : stack.peek();
// 面积值: 左边肯定比自己小，但右边都是比自己大的
max = Math.max(max,(record.length-popLeftIndex-1)*record[popIndex]);
}
return max;
}最大值减去最小值小于或等于num的子数组的数量（Max - Min <= Num ）（双端队列应用）
如果数组长度为N，请实现O(N)的算法
/**
* 最大值减去最小值小于或等于num的子数组的数量
*
* @param arr
* @param num
* @return
* 思路：子数组是多个，当在不断变化时，最大值与最小值也在不断的更新，所以我们应该用一种结构可以实时记录和更新数组中最大值和最小值
* 这里我们可以想到上面的滑动窗口问题，当时是记录窗口内的最大值。所以这里我们使用两个滑动窗口，一个记录最大值，一个记录最小值
* max(arr[i..j]) - min(arr[i...j]) <= num ，如果从i-j每种子集都计算一遍，时间复杂度太高，我们可以找找特定的规律
* - 如果max(arr[i..j]) - min(arr[i...j]) <= num 成立，则arr[i...j]中每一个数组都满足条件,即arr[k...l] (i<=k<=l<=j)
* 我们用arr[i...j-1]举例， max[arr[i...j]] >= max[arr[i...j-1]]， 因为j如果j比i-(j-1)都大，则=成立，如果不是，则> 成立
* - 如果上面情况不成立，则arr[k...l](k<=i<=j<=l) 都不满足条件，这样我们就可以排除许多的可能
*/
public static int getNum(int[] arr, int num) {
// 记录最大值
LinkedList<Integer> maxList = new LinkedList<>();
// 记录最小值
LinkedList<Integer> minList = new LinkedList<>();
int i = 0, j = 0, result = 0;
while (i < arr.length) {
while (j < arr.length) {
// 这里if(false)的唯一可能就是，j在某点时，已经不能继续向前了，所以i开始向右偏移，看是否可以让条件重新满足
if (minList.isEmpty() || minList.peekLast() != j) {
// 更新最小值
while (!minList.isEmpty() && arr[minList.peekLast()] >= arr[j]) {
minList.pollLast();
}
minList.addLast(j);
// 更新最大值
while (!maxList.isEmpty() && arr[maxList.peekLast()] <= arr[j]) {
maxList.pollLast();
}
maxList.addLast(j);
}
// 判断当前结果是否满足条件
if ((arr[maxList.peekFirst()] - arr[minList.peekFirst()]) > num) {
break;
}
j++;
}
result += j - i;
// 检查最大值和最小值是否过期，需要更新的
if (maxList.peekFirst() == i) {
maxList.pollFirst();
}
if (minList.peekFirst() == i) {
minList.pollFirst();
}
i++;
}
return result;
}本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 玲辰书斋！
