检查整数栈中每对相邻数字是否连续
[!Tip]
本节源代码见Github链接🔗
问题描述
给定一个整数栈，如何检查栈中每对相邻数字是否是连续的。每对数字的值可以是递增或递减的。如果栈中元素的个数是奇数，那么组对时忽略栈顶元素。例如，假设栈中元素为[4,5,-2,-3,11,10,5,6,20]，那么算法应该输出真，因为每对二元组(4,5)、(-2,-3)、(11,10)和(5,6)都是连续的数字
核心思路
需要时间复杂度和空间复杂度都为O(n)，借助一个辅助
实现代码
【👉🏻>>点击展开查看代码】
/**
* 检查整数占中每对相邻数字是否连续
*
* @className: CheckStackPairwiseOrder
* @author: Max Solider
* @date: 2023-06-10 22:32
*/public class CheckStackPairwiseOrder {
public static boolean checkStackPairwiseOrder(LLStack stack) {
if (stack.isEmpty()) {
return true;
}
ArrayQueue queue = new ArrayQueue(20);
while (!stack.isEmpty()) {
queue.enQueue(Integer.valueOf(stack.pop()));
}
while (!queue.isEmpty()) {
stack.push(String.valueOf(queue.deQueue()));
}
boolean result = true;
while (!stack.isEmpty()) {
int n = Integer.valueOf(stack.pop());
queue.enQueue(n);
if (!stack.isEmpty()) {
int m = Integer.valueOf(stack.pop());
queue.enQueue(m);
if ((m - n != 1) && (n - m != 1)) {
result = false;
}
}
}
while (!queue.isEmpty()) {
stack.push(String.valueOf(queue.deQueue()));
}
return result;
}
public static void main(String[] args) {
LLStack stack = new LLStack();
stack.push("4");
stack.push("5");
stack.push("-2");
stack.push("-3");
stack.push("11");
stack.push("10");
stack.push("5");
stack.push("6");
stack.push("20");
System.out.println(checkStackPairwiseOrder(stack));
System.out.println(stack);
}
}
时间复杂度
出栈时间复杂度为O(n)，每次移动元素的时间复杂度都是O(n)。
空间复杂度
空间复杂度为O(n)，需要辅助队列。