当前位置：首页 > java >正文

栈相关算法题解题思路与代码实现分享

java 2025/5/6 16:18:04

前言

一、最小栈（LeetCode 155）

题目描述

解题思路

代码实现（C++）

代码解释

二、栈的压入、弹出序列（剑指 Offer JZ31）

题目描述

解题思路

代码实现（C++）

代码解释

总结

前言

在算法学习和面试准备过程中，栈相关的题目是比较常见的类型。栈作为一种后进先出（LIFO）的数据结构，有着广泛的应用。今天我想分享两道我近期做过的栈相关算法题，以及它们的解题思路和代码实现。

一、最小栈（LeetCode 155）

题目描述

设计一个支持 push ， pop ， top 操作，并能在常数时间内检索到最小元素的栈。需要实现 MinStack 类，其中包含以下方法：

- MinStack() 初始化堆栈对象。

- void push(int val) 将元素 val 推入堆栈。

- void pop() 删除堆栈顶部的元素。

- int top() 获取堆栈顶部的元素。

- int getMin() 获取堆栈中的最小元素。

解题思路

为了在常数时间内获取最小元素，我们可以使用两个栈。

一个普通栈 st 用于存储所有元素，另一个辅助栈 minst 用于存储当前的最小元素。

每次 push 操作时，如果要压入的元素小于等于 minst 栈顶元素（或者 minst 为空），就同时将该元素压入 minst 栈。

每次 pop 操作时，如果弹出的元素等于 minst 栈顶元素，那么 minst 栈也同时弹出栈顶元素。这样，。

minst 栈顶始终是当前栈中的最小元素。

代码实现（C++）

class MinStack {public:MinStack() {}void push(int val) {st.push(val);if(minst.empty() || val <= minst.top()){minst.push(val);}}void pop() {if(st.top() == minst.top()){minst.pop();}st.pop();}int top() {return st.top();}int getMin() {return minst.top();}private:stack<int> st;stack<int> minst;};

代码解释

1. 构造函数： MinStack() 用于初始化对象，这里不需要额外操作。

2.  push 方法：将元素 val 压入普通栈 st ，然后判断如果 minst 栈为空或者 val 小于等于 minst 栈顶元素，就将 val 也压入 minst 栈。

3.  pop 方法：如果普通栈 st 弹出的元素等于辅助栈 minst 栈顶元素，说明这个元素是当前最小元素，那么 minst 栈也弹出栈顶元素，然后 st 栈弹出元素。

4.  top 方法：直接返回普通栈 st 的栈顶元素。

5.  getMin 方法：直接返回辅助栈 minst 的栈顶元素，即当前栈中的最小元素。

二、栈的压入、弹出序列（剑指 Offer JZ31）

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。

解题思路

1.我们可以使用一个辅助栈，按照压入序列的顺序依次将元素压入辅助栈。

2.每次压入后检查辅助栈栈顶元素是否与弹出序列当前元素相同。

3.如果相同则将辅助栈栈顶元素弹出，同时移动弹出序列的指针。

4.不断重复这个过程，直到压入序列遍历完。最后检查辅助栈是否为空，如果为空说明弹出序列是可能的，否则不可能。

代码实现（C++）

cppclass Solution {public:bool IsPopOrder(vector<int>& pushV, vector<int>& popV){stack<int> st;int pushi = 0, popi = 0;while(pushi < pushV.size()){st.push(pushV[pushi++]);if(st.top()!= popV[popi]){continue;}else{while(!st.empty() && st.top() == popV[popi]){st.pop();popi++;}}}return st.empty();}};

代码解释

1. 首先定义一个辅助栈 st ，以及两个指针 pushi 和 popi 分别指向压入序列和弹出序列的起始位置。

2. 在 while 循环中，不断将压入序列的元素压入栈中，每次压入后检查栈顶元素是否等于弹出序列当前元素。如果不相等，继续压入下一个元素；如果相等，就进入内层 while 循环，不断弹出栈顶元素，同时移动弹出序列指针，直到栈为空或者栈顶元素不等于弹出序列当前元素。

3. 最后检查栈是否为空，如果为空，说明所有元素都按照正确顺序弹出，返回 true ；否则返回 false 。