算法中栈的应用

红太狼 2024-04-25 08:44 77阅读 0赞

**目录**

栈

练习1：删除字符串中的所有相邻重复项

练习2：比较含退格的字符串

练习3：基本计算器II

练习4：字符串解码

--------------------

## 栈 ##

**栈** 是一种常见的数据结构，遵循先进后出（LIFO）的原则（最后进入栈的元素将被最先移出）

栈有两种基本操作：**压栈（push）**和**出栈（pop）**

> **压栈**：将元素放入栈顶，同时栈顶指针向上移动。
> 
> **出栈**：将栈顶元素移出，并将栈顶指针向下移动。

栈在算法题目中的应用非常广泛，能够简化问题的处理过程，提高算法的效率，在解决算法题目时，合理使用栈能够帮助我们更好的解决问题

接下来，我们通过几道练习来进一步体会栈在算法中的应用

## 练习1：删除字符串中的所有相邻重复项 ##

**题目链接：**

[1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）][1047. _ - _LeetCode]

**题目描述：**

给出由小写字母组成的字符串 `S`，**重复项删除操作**会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

**示例：**

输入："abbaca"
    输出："ca"
    解释：
    例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

**提示：**

1.  `1 <= S.length <= 20000`
2.  `S` 仅由小写英文字母组成。

**思路分析：**当出现两个相邻且相同的字母时，需要将其删除。接下来，我们模拟删除字符串中所有相邻重复项的过程：

![f85ddd57c791400ca8c7b6c009881e37.png][]

若当前字母与与前一位字母相同时，需要将当前字母和前一位字母都删掉，然后再继续遍历下一个字母，若我们使用容器来存储符合条件的字母：

![614f2cf10b0948738a5062e11be0d9a0.png][]

此时，我们可以发现：每次放入元素之前，先与最后一个元素相比较，若相同，则放入；若不同，则不放入，且删除最后一个元素。 此时，**后放入的元素先拿出，满足 后进先出，**因此，我们可以使用 栈 来帮助我们实现相邻重复项的删除

我们可以直接使用 Java 提供的 Stack 类，但由于这道题较为简单，因此，我们可以**直接使用数组 来模拟实现栈**：

> 若栈为空，直接入栈
> 
> 若栈不为空，比较当前元素和栈顶元素，若相同，弹出栈顶元素；若不同，将当前元素放入栈中

**代码实现：**

class Solution {
        public String removeDuplicates(String s) {
            StringBuffer ret = new StringBuffer();//用数组来模拟栈结构
            char[] chs = s.toCharArray();
            for(char ch: chs){//遍历数组
                if(ret.length() > 0 && ch == ret.charAt(ret.length() - 1)){
                    ret.deleteCharAt(ret.length() - 1);//出栈
                }else {
                    ret.append(ch);//进栈
                }
            }
            return ret.toString();
        }
    }

## 练习2：比较含退格的字符串 ##

**题目链接：**

[844. 比较含退格的字符串 - 力扣（LeetCode）][844. _ - _LeetCode]

**题目描述：**

给定 `s` 和 `t` 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 `true` 。`#` 代表退格字符。

**注意：**如果对空文本输入退格字符，文本继续为空。

**示例 1：**

输入：s = "ab#c", t = "ad#c"
    输出：true
    解释：s 和 t 都会变成 "ac"。

**示例 2：**

输入：s = "ab##", t = "c#d#"
    输出：true
    解释：s 和 t 都会变成 ""。

**示例 3：**

输入：s = "a#c", t = "b"
    输出：false
    解释：s 会变成 "c"，但 t 仍然是 "b"。

**提示：**

*  `1 <= s.length, t.length <= 200`
 *  `s` 和 `t` 只含有小写字母以及字符 `'#'`

**思路分析：**

`#` 代表退格符，当出现 \# 时，删除 \# 前的字符。因此，我们同样可以使用栈来帮助我们删除字符。我们可以将给定的字符串中的退格符和需要删除的字符都删除，得到字符串的最终结果，然后再比较两字符串得到的结果是否相同，同样的，我们也可以**使用数组来实现栈**

我们遍历字符串：

> 若当前字符是退格符，且栈不为空，弹出栈顶元素
> 
> 若当前字符是普通字符，将当前字符入栈

![3024c239a25c4a259f73e80e081040dc.jpeg][]

**代码实现：**

class Solution {
        public boolean backspaceCompare(String s, String t) {
            return changeStr(s).equals(t);//比较两字符串删除退格和相应字符后是否相同
        }
        
        public String changeStr(String s){
            StringBuffer ret = new StringBuffer();
            for(int i = 0; i < s.length(); i++){
                char ch = s.charAt(i);
                if(ch != '#'){//普通字符，入栈
                    ret.append(ch);
                }else{
                    if(ret.length() > 0){//若栈不为空，出栈
                        ret.deleteCharAt(ret.length() - 1);
                    }
                }
            }
            return ret.toString();
        }
    }

## 练习3：基本计算器II ##

**题目链接：**

[227. 基本计算器 II - 力扣（LeetCode）][227. _ II - _LeetCode]

**题目描述：**

给你一个字符串表达式 `s` ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 `[-231, 231 - 1]` 的范围内。

**注意：**不允许使用任何将字符串作为数学表达式计算的内置函数，比如 `eval()` 。

**示例 1：**

输入：s = "3+2*2"
    输出：7

**示例 2：**

输入：s = " 3/2 "
    输出：1

**示例 3：**

输入：s = " 3+5 / 2 "
    输出：5

**提示：**

*  `1 <= s.length <= 3 * 105`
 *  `s` 由整数和算符 `('+', '-', '*', '/')` 组成，中间由一些空格隔开
 *  `s` 表示一个 **有效表达式**
 *  表达式中的所有整数都是非负整数，且在范围 `[0, 231 - 1]` 内
 *  题目数据保证答案是一个 **32-bit 整数**

**思路分析：**

由于乘除运算优于加减运算，因此要**先计算表达式中的乘除运算**。因此，我们可以**先计算表达式中的乘除，然后将得到的结果放回原位置，最后进行加减运算**，即可得出结果：

![4a2f8c4ca12f469aa05dbe9440479898.png][]

因此，我们可以使用一个栈来保存进行乘除运算后的值：

> 当运算符为加号时，直接将加号后的元素num放入栈中
> 
> 当运算符是减号时，我们将减号后的元素num的**相反数**放入栈中（放入 -num），这样，当我们**在最后进行加减运算时，只需要进行加法运算，就可以得出结果**
> 
> 当运算符是乘号时，我们将栈顶元素弹出，并与乘号后元素num相乘，然后再将结果放入栈中
> 
> 当运算符是除号时，我们将栈顶元素弹出，与除号后元素num相除，然后再将结果放入栈中

由于 **s是一个有效表达式**，因此，我们不用考虑当运算符为乘除时，栈为空的情况

但由于**第一个元素前无运算符**，因此，我们可以将其之前的运算符设置为 +，这样，就可将其直接放入栈中

> 在提取运算符之后的数字时，若数字为 123 或 45 等多位数，我们需要将数字全部提取出来，此时应该如何提取呢？

我们将num初始化为0，然后向后遍历，每遍历到一个数字k，让num \* 10 + k，这样，就可以提取出每一位数字（例如：需要提取 123，当遍历到1时，num = 0\*10 + 1，遍历到2时，num = 1\*10 + 2，遍历到3时，num = 12\*10 + 3）

因此，我们使用变量op来记录每个数字之前的运算符，op初始化为 + （让第一个数字直接入栈），然后遍历字符串：

> 若op为 + ：数字入栈
> 
> 若op为 - ：数字的相反数入栈
> 
> 若op为 \* 或 /：弹出栈顶元素，并与数字进行计算，然后将计算结果压入栈中

![cc02a2e3dd18479aafafa457abcd3b8e.jpeg][]

**注意：由于提示中告诉我们表达式中存在空格，因此，我们要注意处理空格**

**代码实现：**

class Solution {
        public int calculate(String s) {
            Deque<Integer> stack = new ArrayDeque<>();
            char op = '+';
            int n = s.length(), i = 0;
            while(i < n){//遍历字符串
                if(s.charAt(i) == ' '){//若当前字符为空格，继续向后遍历
                    i++;
                }else if(Character.isDigit(s.charAt(i))){//若当前字符为数字，提取数字
                    int num = 0;
                    while(i < n && Character.isDigit(s.charAt(i))){
                        num = num * 10 + (s.charAt(i) - '0');
                        i++;
                    }
                    //根据op进行操作
                    if(op == '+') stack.push(num);
                    else if(op == '-') stack.push(-num);
                    else if(op == '*') stack.push(stack.pop() * num);
                    else stack.push(stack.pop() / num);
                }else{//若当前字符为运算符，更新op
                    op = s.charAt(i);
                    i++;
                }
            }
            int ret = 0;
            //将所有元素弹出，相加，计算最终结果
            while (!stack.isEmpty()) {
                ret += stack.pop();
            }
            return ret;
        }
    }

## 练习4：字符串解码 ##

**题目链接：**

[394. 字符串解码 - 力扣（LeetCode）][394. _ - _LeetCode]

**题目描述：**

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: `k[encoded_string]`，表示其中方括号内部的 `encoded_string` 正好重复 `k` 次。注意 `k` 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 `k` ，例如不会出现像 `3a` 或 `2[4]` 的输入。

**示例 1：**

输入：s = "3[a]2[bc]"
    输出："aaabcbc"

**示例 2：**

输入：s = "3[a2[c]]"
    输出："accaccacc"

**示例 3：**

输入：s = "2[abc]3[cd]ef"
    输出："abcabccdcdcdef"

**示例 4：**

输入：s = "abc3[cd]xyz"
    输出："abccdcdcdxyz"

**提示：**

*  `1 <= s.length <= 30`
 *  `s` 由小写英文字母、数字和方括号 `'[]'` 组成
 *  `s` 保证是一个 **有效** 的输入。
 *  `s` 中所有整数的取值范围为 `[1, 300]`

**思路分析：**题目要求我们出现 k\[str\]时，将\[\]中的字符串str重复k次， 因此：

> 当出现数字时，需要提取数字
> 
> 当出现 \[ 时，需要提取 \[ 后的字符串
> 
> 当出现 \] 时，需要将 \[\] 中的字符串重复k次

因此，我们可以使用 **两个栈** 来分别保存 数字 和 字符串：

当出现数字时，提取数字，放入保存数字的栈nums中（提取方法与 练习3：基本计算器II 中提取数字相同）

当出现 \[ 时，将\[ 后的字符串放入保存字符串的栈stack中

当出现 \] 时，将 stack 的栈顶元素 和 nums 栈顶元素 弹出，进行复制，然后再将复制结果放入stack中

但字符串中可能出现 嵌套的情况（如：3\[a2\[c\]\]）或普通字符（即不用进行重复操作的字符，如：ab2\[c\]中的ab）

> **如何处理嵌套呢？**

以3\[a2\[c\]\]为例，若当前字符为\[，我们提取 \[ 后的字符串a，放入stack中，继续遍历，

此时出现数字，提取数字3，放入nums中，

然后又遇到 \[，此时提取字符串c，放入stack 中，

当遇到 \] 时，**我们将stack栈顶元素c弹出、nums栈顶元素2弹出，将c重复2次，然后将其拼接到此时的栈顶元素a后**，即 将 cc 拼接到 a 后，然后将 acc 放入栈中，

当遇到 \] 时，将stack栈顶元素acc弹出、nums栈顶元素3弹出，将acc重复3次，此时stack为空，直接将其压入stack中

同理，我们以类似的思路来处理普通字符，当出现普通字符时，若stack为空，我们直接将其放入栈中；若栈不为空，我们将其拼接到栈顶元素后

![227bb91ae4aa4cac9e38be00db746e94.png][]

由于我们在每次将字符串进行复制后进行拼接，或拼接普通字符时都有判断stack是否为空，因此，我们可以**先在栈stack中存放一个空串**，这样，就不需要每次都判断字符串是否为空了

**代码实现：**

class Solution {
        public String decodeString(String s) {
            char[] chs = s.toCharArray();
            Stack<StringBuffer> stack = new Stack<>();
            Stack<Integer> nums = new Stack<>();
            int i = 0, n = chs.length;
            stack.push(new StringBuffer());
            while(i < n){
                if(chs[i] >= '0' && chs[i] <= '9'){//当前字符为数字，提取数字，并将其放入栈nums中
                    int num = 0;
                    while(i < n && (chs[i] >= '0' && chs[i] <= '9')){
                        num = num * 10 + (chs[i] - '0');
                        i++;
                    }
                    nums.push(num);
                }else if(chs[i] == '['){//当前字符为[,提取字符串，并将其放入栈stack中
                    i++;
                    StringBuffer tmp = new StringBuffer();
                    while(i < n && (chs[i] >= 'a' && chs[i] <= 'z')){
                        tmp.append(chs[i]);
                        i++;
                    }
                    stack.push(tmp);
                }else if(chs[i] == ']'){//当前字符为 ] 将k个该字符串拼接到栈顶元素后
                    StringBuffer tmp = stack.pop();
                    int k = nums.pop();
                    while(k-- > 0){
                        stack.peek().append(tmp);
                    }
                    i++;
                }else{//当前字符为普通字符，将所有普通字符拼接到stack栈顶元素后
                    StringBuffer tmp = new StringBuffer();
                    while(i < n && (chs[i] >= 'a' && chs[i] <= 'z')){
                        tmp.append(chs[i]);
                        i++;
                    }
                    stack.peek().append(tmp);
                }
            }
            return stack.peek().toString();
        }
    }

[1047. _ - _LeetCode]: https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
[f85ddd57c791400ca8c7b6c009881e37.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/4fd21811851c47f1b276d6ccba8aba6a.png
[614f2cf10b0948738a5062e11be0d9a0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/a95f5ab064184273952a4f156ff72d10.png
[844. _ - _LeetCode]: https://leetcode.cn/problems/backspace-string-compare/description/
[3024c239a25c4a259f73e80e081040dc.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/1781677ee01248d5bd15bd8e18a60f01.jpeg
[227. _ II - _LeetCode]: https://leetcode.cn/problems/basic-calculator-ii/description/
[4a2f8c4ca12f469aa05dbe9440479898.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/052b616ca515497cb77ed0791bdc9088.png
[cc02a2e3dd18479aafafa457abcd3b8e.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/91bd8d0bf9834278bbe6c93f3e76ef55.jpeg
[394. _ - _LeetCode]: https://leetcode.cn/problems/decode-string/description/
[227bb91ae4aa4cac9e38be00db746e94.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/6cd70177df36445ebb3464cad1fad250.png