单调栈的经典例题

小鱼儿 2022-08-28 07:53 155阅读 0赞

**本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。**

前言

算法中的单调栈应用十分的广泛；单调栈简单的来说就是栈内元素单调递增或者单调递减的栈，同时单调栈还可以不断的维护一组某种或多种规律的数据，利用这一性质可以解决许多算法问题。**本文主要讲解单调栈的算法用法，需对单调栈具有一定的了解。**

问题描述

## 问题一 ##

给你一个字符串 s ，一个整数 k ，一个字母 letter 以及另一个整数 repetition 。返回 s 中长度为 k 且 字典序最小 的子序列，该子序列同时应满足字母 letter 出现 至少 repetition 次。生成的测试用例满足 letter 在 s 中出现至少 repetition 次。

子序列 是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。

字符串 a 字典序比字符串 b 小的定义为：在 a 和 b 出现不同字符的第一个位置上，字符串 a 的字符在字母表中的顺序早于字符串 b 的字符。

样例：

输入：s = "leetcode", k = 4, letter = "e", repetition= 2

输出："ecde"

解释："ecde" 是长度为 4 且满足字母 "e" 出现至少 2 次的字典序最小的子序列。

**题目来源 力扣：5893. 含特定字母的最小子序列**

**https://leetcode-cn.com/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/**

### 题目分析 ###

题意：此题主要描述的是需要维护一个长度为k的字典序最小且至少出现repetition 次letter字母的s的子序列，**关键词就是维护一个长度为k的字典序最小的子序列，子序列中包含至少repetition 个letter字母；**此题的正好符合单调栈的性质，利用单调栈来维护以上性质！

维护三种性质：

**性质1**：维护字典序单增的字符串。(满足题意中的字典序最小这一性质)

**性质2**：维护长度为k的字符串。(满足题中长度为k的字符串这一性质)

**性质3**：维护子序列中包含至少repetition 个letter字母。(同理满足题意性质)

<table> 
 <tbody> 
 <tr> 
 <td>const int N = 50010;class Solution { public:&nbsp;&nbsp;&nbsp; int cnt[N];&nbsp;&nbsp;&nbsp; string &nbsp;smallestSubsequence(string s, int k, char letter, int repetition) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int n = s.size();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int i = n-1; i &gt;= &nbsp;0; i --){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (s[i] == letter) &nbsp;cnt[i] = cnt[i + 1] + 1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else cnt[i] = cnt[i+1]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //cnt[i]统计在i的右侧还有多少个letter，便于后续维护&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; string ans;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int p = 0; // p用于记录当前维护字符串中的letter数量&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // 单调栈模板&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int i = 0; i &lt; n; i &nbsp;++){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; char c = s[i];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // 维护字典序单调增的字符串&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; while(!ans.empty() &nbsp;&amp;&amp; c &lt; ans.back()){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // 维护长度为不低于k的字符串&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (ans.size() - 1 &nbsp;+ n - i &lt; k) break;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (ans.back() == &nbsp;letter){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // 维护子序列中包含至少repetition &nbsp;个letter字母&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (p - 1 + &nbsp;cnt[i] &lt; repetition) break;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; p --;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ans.pop_back();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (c == letter) p ++, &nbsp;cnt[i] --;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ans.push_back(c);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // 因为最终维护的字符串为长度不低于k的字符串，其长度可能超过k，故此将其长度缩减至k&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; while(ans.size() &gt; k) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (ans.back() == &nbsp;letter) p --;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ans.pop_back();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // 在缩减至k的操作过程中，可能将letter减去，导致字符串中的letter个数少于repetition&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // 所以如果letter个数少于repetition需要将字符串的末尾值换位letter即可满足&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int i = ans.size() - &nbsp;1; i &gt;= 0; i --){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (p &lt; repetition &nbsp;&amp;&amp; ans[i] != letter) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ans[i] = letter;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; p ++;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return ans;&nbsp;&nbsp;&nbsp; }};</td> 
 </tr> 
 </tbody> 
</table>

##     ##

## 问题二 ##

返回 s 字典序最小的子序列，该子序列包含 s 的所有不同字符，且只包含一次。

样例

输入：s ="cbacdcbc"

输出："acdb"

**题目来源** **力扣：1081.** **不同字符的最小子序列**

**https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/**

### 题目分析 ###

此题与上一题类似，求一个最小字典序的子序列，且子序列的必须包含s中所有不同的字符只包含一次。

维护二种性质：

**性质一**：维护一个字典序最小的子序列。

**性质二**：维护包含所有不同字符且只包含一次的子序列。

<table> 
 <tbody> 
 <tr> 
 <td>class Solution { public:&nbsp;&nbsp;&nbsp; // cnt记录在s中从i向右中还存在的多少个对应字符&nbsp;&nbsp;&nbsp; int cnt[28];&nbsp;&nbsp;&nbsp; // snt记录字符在维护的字符串中是否存在&nbsp;&nbsp;&nbsp; bool snt[28];&nbsp;&nbsp;&nbsp; string &nbsp;smallestSubsequence(string s) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; string t;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int n = s.size(), k = 0;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int i = n-1; i &gt;= &nbsp;0; i --){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int x = s[i] - 'a';&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (cnt[x] == 0) k ++;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cnt[x] ++;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for (int i = 0; i &lt; n; i &nbsp;++){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; char c = s[i];&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int u = c - 'a';&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // 维护最小字典序的子序列&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; while(!t.empty() &nbsp;&amp;&amp; t.back() &gt; c) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; int x = t.back() - &nbsp;'a';&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // 维护包含所有不同字符且只包含一次的子序列&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (cnt[x] &lt;= 0 &nbsp;|| snt[u]) break;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; t.pop_back();&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; snt[x] = false;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (!snt[u]) &nbsp;t.push_back(c);&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; snt[u] = true, cnt[u] &nbsp;--;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return t;&nbsp;&nbsp;&nbsp; }};</td> 
 </tr> 
 </tbody> 
</table>

结语

本文主要分享了两道力扣经典的单调栈算法题，其共同的性质都是求最小字典序的子序列，且其余性质均满足单调栈维护；需要对单调栈有了解的朋友进行阅读，了解其单调栈的模板与维护方法。

实习编辑：衡辉

稿件来源：深度学习与文旅应用实验室（DLETA）