栈 - Stack

最近更新：2025-10-20 | 字数总计：3.9k | 阅读估时：17分钟 | 阅读量：次

基础算法 - 栈
1. 相关题目

基础算法 - 栈

在计算机科学中，数据结构是算法和程序设计的基石。栈（Stack）作为其中一种重要的数据结构，以其独特的“后进先出”（Last In First Out, LIFO）特性，在各种应用中扮演着关键角色。从函数调用栈到表达式求值，栈的应用无处不在。

在开始之前，我们先来回顾一下栈的定义和特点。栈是一种线性数据结构，具有以下两个主要操作：

压栈（Push）：将元素添加到栈的顶端。
弹栈（Pop）：移除并返回栈顶元素。

通过这些基本操作，栈能够高效地管理数据的存取顺序。接下来，我们将详细介绍栈的实现方法和应用场景。

此篇记录使用栈解题的思路。

相关题目

20. 有效的括号 - 力扣（LeetCode）

难度：简单

class Solution {
    public boolean isValid(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        
        char[] sChars = s.toCharArray();
        
        for(char ch: sChars){
            if(stack.isEmpty()){   // 如果当前栈为空，入栈的是下面这三个闭合括号，直接返回false
                if(ch==')'||ch==']'||ch=='}')
                    return false;
                else
                    stack.push(ch);
            }else{
                char peek = stack.peek();   // 相同的相互抵消
                if(ch==')'&&peek=='(')
                    stack.pop();
                else if(ch==']'&&peek=='[')
                    stack.pop();
                else if(ch=='}'&&peek=='{')
                    stack.pop();
                else stack.push(ch);
            }
        }
        if(stack.isEmpty())
            return true;
        else return false;
    }
}

为什么使用栈？

栈的特点使得它非常适合处理成对出现的匹配问题。具体来说：

后进先出（LIFO）：当我们遇到一个闭括号时，我们需要检查最近的一个开括号是否与之匹配。这正是栈的后进先出性质能够完美实现的功能。我们可以通过弹出栈顶元素来检查匹配情况。
开括号和闭括号的顺序：栈能帮助我们记录未匹配的开括号，当遇到闭括号时，直接检查栈顶的开括号是否匹配。如果匹配，则弹出栈顶元素，表示这一对括号已经匹配。

155. 最小栈 - 力扣（LeetCode）

难度：中等

class MinStack {
    
    LinkedList<Integer> stack;
    LinkedList<Integer> min;
    
    public MinStack() {  // 初始化
        stack = new LinkedList<>();
        min = new LinkedList<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(min.isEmpty()){
            min.push(val);
        }else{
            int peek = min.peek();   // min栈顶同步更新stack中最小值
            if(peek<val){
                min.push(peek);
            }else{
                min.push(val);
            }
        }
    }
    
    public void pop() {
        stack.pop();
        min.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {  // 直接从min栈中取即可
        return min.peek();
    }
}

为了在常数时间内获取最小值，我们引入了一个辅助栈 min。辅助栈 min 的每个元素对应于主栈 stack 中的元素，使得 min 栈顶始终保持当前栈的最小值。因此，通过同步更新 min 栈，我们可以在 O(1) 时间复杂度内获取栈中的最小值。

394. 字符串解码 - 力扣（LeetCode）

难度：中等（中等偏上）

嵌套括号是本题的难点

class Solution {
    
    LinkedList<String> Sstack; // 存储字符串的栈
    LinkedList<Integer> Istack; // 存储倍数的栈
    String tmp = ""; // 临时存储当前的子字符串
    int k = 0; // 临时存储当前的倍数

    public String decodeString(String s) {
        Sstack = new LinkedList<>();
        Istack = new LinkedList<>();

        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) { // 如果是数字
                k = k * 10 + ch - '0'; // 计算倍数
            } else if (ch == '[') { // 遇到 '['，保存状态
                Istack.push(k); // 保存当前倍数
                k = 0; // 重置倍数
                Sstack.push(tmp); // 保存当前字符串
                tmp = ""; // 重置当前字符串
            } else if (ch == ']') { // 遇到 ']'
                StringBuffer sb = new StringBuffer(Sstack.pop()); // 取出之前保存的字符串
                int times = Istack.pop(); // 取出倍数
                for (int i = 0; i < times; i++) {
                    sb.append(tmp); // 拼接当前子字符串多次
                }
                tmp = sb.toString(); // 更新当前字符串
            } else { // 普通字符，直接累加到当前字符串
                tmp += ch;
            }
        }
        return tmp; // 返回最终解码后的字符串
    }
}

e7c91ad3adf0af47d98f38be9ad1541b

为什么用栈

在处理嵌套的结构（如括号中的括号）时，栈是一种非常自然且有效的数据结构。对于这道题目，使用栈的关键作用如下：

处理嵌套结构：栈的后进先出（LIFO）特性非常适合处理嵌套的括号结构。在遇到 [ 时，我们将当前的状态（当前字符串和当前的数字）入栈，以便在遇到 ] 时能够恢复并继续处理。
保存状态：当遇到 [ 时，我们需要保存当前的字符串和倍数，因为接下来的内容是一个新的子字符串，直到遇到对应的 ] 才会结束。使用栈可以方便地保存和恢复这些状态。
简化操作：通过栈，我们可以很方便地进行字符串的累积和倍数的计算，不需要额外的复杂数据结构或逻辑。

739. 每日温度 - 力扣（LeetCode）

难度：中等

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] res =  new int[len];
        // stack
        LinkedList<Integer> stack = new LinkedList<>();
        int p = 0;
        while(p<len){
            if(stack.isEmpty()){
                stack.push(p);
                p++;
            }else{
                // 使得这个栈的，栈底>栈顶
                if(temperatures[stack.peek()]>=temperatures[p]) {
                    stack.push(p);
                    p++;
                }else{
                    // 如果新的大元素来了，依次pop，并更新res数组
                    while (!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[p]){
                        int tmp = stack.pop();
                        res[tmp] = p-tmp;
                    }
                }
            }
        }
        return res;
    }
}

这个题挺简单的，就是利用栈的特性，维护一个从栈底到栈顶是大->小的顺序，如果新来的下一个元素比当前的栈顶大，那么就依次pop，pop的同时更新res数组，因为这个新来的大元素就是栈中小元素的”下一个”大元素。

为了方便起见，我们在栈中存放的是index

496. 下一个更大元素 I - 力扣（LeetCode）

难度：简单

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        LinkedList<Integer> stack = new LinkedList<>();
        int[] help = new int[10001];
        // help[i]=j表示，值为i的元素下一个更大的是j，如果没有下一个更大的，那么j为0
        // 维护栈：栈底 > 栈顶
        for(int i=0;i<nums2.length;i++){
            if(!stack.isEmpty()){
                int peek = stack.peek();
                while(peek<nums2[i]){
                    help[stack.pop()] = nums2[i];
                    if(stack.isEmpty()) break;
                    peek = stack.peek();
                }
            }
            stack.push(nums2[i]);
        }
        // 根据help数组中的值得到最终返回数组res
        int[] res = new int[nums1.length];
        for(int i=0;i<nums1.length;i++){
            res[i] = (help[nums1[i]]==0)?-1:help[nums1[i]];
        }
        return res;
    }
}

这一题与 [每日温度](#739. 每日温度 - 力扣（LeetCode）) 很像，都是通过维护单调栈得到下一个更大的元素的值或者下标。

503. 下一个更大元素 II - 力扣（LeetCode）

难度：中等

与 [下一个更大元素 Ⅰ](#496. 下一个更大元素 I - 力扣（LeetCode）) 相比，这里的数组是循环数组，这意味着最后一个元素的下一个是第一个元素。所以，进行两次数组的出栈入栈操作即可。

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1); // 初始化结果数组，默认为 -1
        Stack<Integer> stack = new Stack<>(); // 栈用于存储索引
        
        // 遍历数组，找出每个元素的下一个更大元素
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i]; // 更新结果数组中相应位置的值
            }
            stack.push(i); // 当前索引入栈x
        }
        
        // 再次遍历数组，处理循环数组的情况
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                result[stack.pop()] = nums[i]; // 更新结果数组中相应位置的值
            }
        }
        
        return result; // 返回结果数组
    }
}

556. 下一个更大元素 III - 力扣（LeetCode）

难度：中等

这个题与栈没关系了。更像 [下一个排列](#31. 下一个排列 - 力扣（LeetCode）)

class Solution {
    public int nextGreaterElement(int n) {
        char[] con = Integer.toString(n).toCharArray();
        int len = con.length;
        int p = len-1;
        for(;p>=1;p--){
            if(con[p-1]<con[p])break;
        }
        // 表明全是降序
        if(p==0)return -1;
        // 寻找交换的数
        int q = len-1;
        for(;q>=p;q--){
            if(con[q]>con[p-1])break;
        }
        // swap
        char tmp = con[q];
        con[q] = con[p-1];
        con[p-1] = tmp;
        // reverse
        reverse(con,p,len-1);
        
        System.out.println(Arrays.toString(con));
        long ans =  Long.parseLong(String.valueOf(con));
        if(ans>Integer.MAX_VALUE) return -1;  // 不满足32位整数也返回-1
        return (int)ans;
    }

    private void reverse(char[] con,int start,int end){
        for(int i=start,j=end;i<j;i++,j--){
            char tmp = con[i];
            con[i] = con[j];
            con[j] = tmp;
        }
    }
}

31. 下一个排列 - 力扣（LeetCode）

数组双指针

主要还是弄懂题目的解法步骤，如何去拆分成可以被程序表达的步骤

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        int p = len-1;
        for(;p>=1;p--){
            if(nums[p-1]<nums[p])break;
        }
        // 如果p==0表明nums全是降序的
        if(p==0){
            reverse(nums,0,len-1);
            return;
        }
        int q=len-1;
        for(;q>p-1;q--){
            if(nums[p-1]<nums[q])break;
        }
        //swap
        int tmp = nums[p-1];
        nums[p-1] = nums[q];
        nums[q] = tmp;
        // reverse
        reverse(nums,p,len-1);
        return;
    }

    private void reverse(int[] nums,int start,int end){
        for(int i=start,j=end;i<j;i++,j--){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
}

84. 柱状图中最大的矩形 - 力扣（LeetCode）

难度：困难

class Solution {
    public int largestRectangleArea(int[] heights) {
        LinkedList<Integer> stack = new LinkedList<>();   // stack中存放索引
        stack.push(-1);  // 第一个哨兵进栈
        int res = Integer.MIN_VALUE;
        
        for(int i=0;i<=heights.length;i++){
            int cur;
            if(i!=heights.length){   // 最后一个哨兵
                cur = heights[i];
            }else{
                cur = -1;
            }
            int peekIdx = stack.peek();
            int peek;
            if(peekIdx!=-1){  
                peek = heights[peekIdx];
            }else{ 
                peek = -1;  // 如果当前是哨兵索引
            }
            while(peek>cur){
                stack.pop();
                int h = peek;
                int w = i - stack.peek() - 1;
                res = Math.max(h*w,res);
                peekIdx = stack.peek();
                if(peekIdx!=-1){
                    peek = heights[peekIdx];
                }else{
                    peek = -1;
                }
            }
            stack.push(i);
        }
        return res;
    }
}

维护一个单调栈，栈底 << 栈顶，当有新的值要入栈时，如果新的值比当前栈顶的值小，那么就计算以当前栈顶高度为高的最大矩形面积，宽就为当前值的索引减去当前栈顶弹出后新栈顶的值(这个索引对应的高度一定小于当前栈顶，所以这里是这个高度所能向左边延申的边界) 再减 1

所以该题关键是找到某个高度能延申的左右边界，以高度为单位求最大矩形面积。

316. 去除重复字母 - 力扣（LeetCode）

难度：中等

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] count = new int[26]; // 用于记录每个字母的出现次数
        for (char ch : s.toCharArray()) {
            count[ch - 'a']++; // 计算每个字母的出现次数
        }

        boolean[] flag = new boolean[26]; // 用于标记字母是否已经在栈中
        
        LinkedList<Character> stack = new LinkedList<>(); // 用于构建结果的单调栈
        
        for (char ch : s.toCharArray()) {
            if (!flag[ch - 'a']) { // 如果当前字母还没有被加入到最终结果中
                while (!stack.isEmpty() && stack.peek() > ch && count[stack.peek() - 'a'] > 0) {
                    flag[stack.pop() - 'a'] = false; // 将那些比当前字母大且后续还会出现的字母从栈中移除
                }
                stack.push(ch); // 将当前字母加入栈中
                flag[ch - 'a'] = true; // 标记当前字母已被加入栈中
            }
            count[ch - 'a']--; // 当前字母的剩余数量减一
        }
        
        StringBuilder res = new StringBuilder(); // 用于构建最终结果字符串
        while (!stack.isEmpty()) {
            res.append(stack.removeLast()); // 从栈底开始构建最终结果
        }
        
        return res.toString(); // 返回最终结果
    }
}

维护单调栈，但是这个题维护单调栈有一些额外的要求，比如说每个不同的字母只能出现一次（flag数组辅助），还要保证必须出现一次，即不能错过这个字母（count数组辅助）。

402. 移掉 K 位数字 - 力扣（LeetCode）

难度：中等

class Solution {
    public String removeKdigits(String num, int k) {
        int len = num.length();
        if(k>=len)return "0";
        
        LinkedList<Character> stack = new LinkedList<>();
        
        int cnt = 0;  // 表示当前移除了多少位数字了
        
        for(char ch : num.toCharArray()){
            while(!stack.isEmpty()&&stack.peek()>ch&&cnt<k){
                stack.pop();
                cnt++;
            }
            stack.push(ch);
        }
        
        // 避免cnt<k
        for(;cnt<k;cnt++){
            stack.pop();
        }
        
        // 清除前置0
        while(!stack.isEmpty()&&stack.getLast()=='0'){
            stack.removeLast();
        }
        
        // 组装最后的res
        String res = "";
        while(!stack.isEmpty()){
            res += stack.removeLast();
        }
        
        return (res=="")?"0":res;
        
    }
}

用数组模拟栈，stack中存放索引，这样可以使得代码运行更快。

class Solution {
    public String removeKdigits(String num, int k) {
        int len = num.length();
        if(k>=len)return "0";
        
        int[] stack = new int[len];
        int top = -1;
        char[] con = num.toCharArray();
        
        for(int i=0;i<len;i++){
            while(top!=-1&&con[stack[top]]>con[i]&&k>0){
                k--;
                top--;
            }
            top++;
            stack[top] = i;
        }
        
        // 用掉可能多余的k
        top -= k;
        
        // 去除前置0
        int start = 0;
        for(;start<=top;start++){
            if(con[stack[start]]=='0')
                continue;
            else
                break;
        }
        if(start>top)
            return "0";
        
        StringBuffer sb =new StringBuffer();
        for(int i=start;i<=top;i++){
            sb.append(con[stack[i]]);
        }
        return sb.toString();
        
        
    }
}

该题也是在维护单调栈的同时要满足一些要求，比如说规定了从栈中pop出的元素的数量。

1019. 链表中的下一个更大节点 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    
    int[] res;
    LinkedList<Integer> stack = new LinkedList<>();
    
    public int[] nextLargerNodes(ListNode head) {
        f(head,0);
        return res;
    }
    
    private void f(ListNode p,int i){
        if(p==null){
            res = new int[i];
            return;
        }
        // 先递归到底，初始化res数组
        // 然后再从最后往前遍历节点
        f(p.next,i+1);
        while(!stack.isEmpty()&&stack.peek()<=p.val){
            stack.pop();
        }
        if(!stack.isEmpty()){
            res[i] = stack.peek();
        }
        stack.push(p.val);
    }
}

由于现在操作的目标是链表，无法获得其索引值，需要一些技巧初始化res，并且需要用合适的方式遍历链表维护单调栈。

主要思路

递归到底，初始化结果数组：
- 使用递归遍历链表，直到链表的末尾。在到达末尾节点时，确定结果数组 res 的长度。
从后向前处理节点：
- 递归函数在递归到底返回时，从最后一个节点开始向前处理。这相当于反向遍历链表，方便我们使用栈来找到每个节点的下一个更大节点。
利用栈来找到下一个更大节点：
- 使用栈来存储节点值，保证栈中的元素是单调递减的，这样可以快速找到每个节点的下一个更大节点。

从前向后遍历维护单调栈 与 从后向前遍历维护单调栈 有什么不同？

前者确定下一个更大的元素是在更大的元素加入栈后将小的元素依次pop出的时候确定的。

后者确定下一个更大的元素是在将新元素与当前栈顶元素进行比较，将不行的pop出，直到找到大于当前新元素的栈顶，这时才能确定。

也就是说，前者可能出现新元素入栈时候确定了很多个元素的下一个最大元素，而后者是新元素入栈时只能确定新元素的下一个最大元素。

2024-06-11 该篇文章被 jay1an 打上标签: 基础算法栈单调栈归为分类: 基础算法