剑指offer-21、栈的压⼊、弹出序列
<h2 id="题描述">题⽬描述</h2><p>输⼊两个整数序列，第⼀个序列表示栈的压⼊顺序，请判断第⼆个序列是否可能为该栈的弹出顺序。假设压⼊栈的所有数字均不相等。例如序列1,2,3,4,5 是某栈的压⼊顺序，序列4,5,3,2,1 是该压栈序列对应的⼀个弹出序列，但4,3,5,1,2 就不可能是该压栈序列的弹出序列。（注意：这两个序列的⻓度是相等的）</p>
<p>示例1<br>
输⼊：,<br>
返回值：true<br>
说明：可以通过push(1) => push(2) => push(3) => push(4) => pop() => push(5)=> pop() => pop() => pop() => pop()；这样的顺序得到 这个序列，返回 true</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="辅助栈模拟推荐">辅助栈模拟（推荐）</h3>
<p>使用一个辅助栈来模拟压入和弹出过程：</p>
<ol>
<li>初始化一个空栈和指向弹出序列的指针</li>
<li>遍历压入序列，依次将元素压入栈中</li>
<li>每次压入后，检查栈顶元素是否等于当前弹出序列元素
<ul>
<li>如果相等，则弹出栈顶元素并移动弹出序列指针</li>
<li>重复此过程直到不相等为止</li>
</ul>
</li>
<li>最后检查栈是否为空，为空则表示弹出序列可行</li>
</ol>
<pre><code class="language-java">public class Solution {
public boolean IsPopOrder(int[] pushA, int[] popA) {
// 边界条件检查
if (pushA == null || popA == null || pushA.length == 0 || popA.length == 0 || pushA.length != popA.length) {
return false;
}
Stack<Integer> stack = new Stack<>(); // 辅助栈
int popIndex = 0; // 弹出序列指针
for (int pushValue : pushA) {
stack.push(pushValue); // 压入当前元素
// 循环检查栈顶是否等于当前弹出元素
while (!stack.isEmpty() && stack.peek() == popA) {
stack.pop(); // 弹出匹配元素
popIndex++; // 移动弹出序列指针
}
}
return stack.isEmpty(); // 栈空表示全部匹配
}
}
</code></pre>
<ul>
<li>时间复杂度： O(n)</li>
<li>空间复杂度： O(n) , 借助了额外的栈空间，最坏情况下会全部⼊栈。</li>
</ul>
<h3 id="双指针法">双指针法</h3>
<p>利用原数组作为栈空间，通过双指针模拟栈操作：</p>
<ol>
<li>使用压入序列本身作为栈空间</li>
<li>通过栈指针和弹出序列指针同步移动</li>
<li>直接在原数组上进行"压入"和"弹出"操作</li>
</ol>
<pre><code class="language-java">public class Solution {
public boolean IsPopOrder(int[] pushA, int[] popA) {
if (pushA == null || popA == null || pushA.length != popA.length) {
return false;
}
int stackTop = -1; // 栈指针
int popIndex = 0; // 弹出序列指针
for (int pushValue : pushA) {
pushA[++stackTop] = pushValue; // 利用原数组存储
// 检查并"弹出"
while (stackTop >= 0 && pushA == popA) {
stackTop--;
popIndex++;
}
}
return stackTop == -1;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)</li>
<li><strong>空间复杂度</strong>：O(1)，仅使用固定数量的指针变量</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19030193
頁:
[1]