平衡括号串（⼀）

先来个简单的，⼒扣第 921 题「使括号有效的最少添加」：

给你输⼊⼀个字符串 s，你可以在其中的任意位置插⼊左括号 ( 或者右括号 )，请问你最少需要⼏次插⼊才
能使得 s 变成⼀个有效的括号串？

⽐如说输⼊ s = "())("，算法应该返回 2，因为我们⾄少需要插⼊两次把 s 变成 "(())()"，这样每个左
括号都有⼀个右括号匹配，s 是⼀个有效的括号串。
这其实和前⽂的判断括号有效性⾮常类似，我们直接看代码：

#include <stdio.h>

int minAddToMakeValid(char* s) {
int res = 0;  // 记录插入次数
int need = 0;  // 右括号的需求量

// 遍历字符串中的每个字符
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == '(') {
need++;  // 对右括号的需求 + 1
}
if (s[i] == ')') {
need--;  // 对右括号的需求 - 1
if (need == -1) {  // 当需求量为-1时，表示需要插入一个左括号
need = 0;
res++;  // 需要插入一个左括号，插入次数加1
}
}
}

return res + need;  // 返回插入次数加上剩余的右括号需求量
}

int main() {
char inputString[] = "((()))";  // 输入要处理的字符串
int result = minAddToMakeValid(inputString);
printf("Minimum number of additions to make the string valid: %d\n", result);
return 0;
}

这段代码就是最终解法，核⼼思路是以左括号为基准，通过维护对右括号的需求数 need，来计算最⼩的插⼊
次数。需要注意两个地⽅：

1、当 need == -1 的时候意味着什么？
因为只有遇到右括号 ) 的时候才会 need--，need == -1 意味着右括号太多了，所以需要插⼊左括号。
⽐如说 s = "))" 这种情况，需要插⼊ 2 个左括号，使得 s 变成 "()()"，才是⼀个有效括号串。

2、算法为什么返回 res + need？
因为 res 记录的左括号的插⼊次数，need 记录了右括号的需求，当 for 循环结束后，若 need 不为 0，那么
就意味着右括号还不够，需要插⼊。
⽐如说 s = "))(" 这种情况，插⼊ 2 个左括号之后，还要再插⼊ 1 个右括号，使得 s 变成 "()()()"，才
是⼀个有效括号串。
以上就是这道题的思路，接下来我们看⼀道进阶题⽬，如果左右括号不是 1:1匹配，会出现什么问题呢？

平衡字符串（二）

这是⼒扣第 1541 题「平衡括号字符串的最少插⼊次数」：
现在假设 1 个左括号需要匹配 2 个右括号才叫做有效的括号组合，那么给你输⼊⼀个括号串 s，请问你如何
计算使得 s 有效的最⼩插⼊次数呢？

核⼼思路还是和刚才⼀样，通过⼀个 need 变量记录对右括号的需求数，根据 need 的变化来判断是否需要
插⼊。

第⼀步，我们按照刚才的思路正确维护 need 变量：

int minInsertions(string s) {
 // need 记录需右括号的需求量
 int res = 0, need = 0;
 
 for (int i = 0; i < s.size(); i++) {
 // ⼀个左括号对应两个右括号
 if (s[i] == '(') {
 need += 2;
 }
 
 if (s[i] == ')') {
 need--;
 }
 }
 
 return res + need;
}

现在想⼀想，当 need 为什么值的时候，我们可以确定需要进⾏插⼊？

⾸先，类似第⼀题，当 need == -1 时，意味着我们遇到⼀个多余的右括号，显然需要插⼊⼀个左括号。

⽐如说当 s = ")"，我们肯定需要插⼊⼀个左括号让 s = "()"，但是由于⼀个左括号需要两个右括号，所
以对右括号的需求量变为 1：

if (s[i] == ')') {
 need--;
 // 说明右括号太多了
 if (need == -1) {
 // 需要插⼊⼀个左括号
 res++;
 // 同时，对右括号的需求变为 1
 need = 1;
 }
}

另外，当遇到左括号时，若对右括号的需求量为奇数，需要插⼊ 1 个右括号。因为⼀个左括号需要两个右括
号嘛，右括号的需求必须是偶数，这⼀点也是本题的难点。

所以遇到左括号时要做如下判断：

if (s[i] == '(') {
 need += 2;
 if (need % 2 == 1) {
 // 插⼊⼀个右括号
 res++;
 // 对右括号的需求减⼀
 need--;
 }
}

综上，我们可以写出正确的代码：

int minInsertions(char* s) {
int res = 0, need = 0;
int len = strlen(s);
for (int i = 0; i < len; i++) {
if (s[i] == '(') {
need += 2;
if (need % 2 == 1) {
res++;
need--;
}
}
if (s[i] == ')') {
need--;
if (need == -1) {
res++;
need = 1;
}
}
}
return res + need;
}

单调栈结构解决三道算法题

栈（stack）是很简单的一种数据结构，先进后出的逻辑顺序，符合某些问题的特点，比如说函数调用栈。单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

听起来有点像堆（heap）？不是的，单调栈用途不太广泛，只处理一类典型的问题，比如「下一个更大元素」，「上一个更小元素」等。本文用讲解单调队列的算法模版解决「下一个更大元素」相关问题，并且探讨处理「循环数组」的策略。至于其他的变体和经典例题，我会在 数据结构精品课 中讲解。

单调栈模板

现在给你出这么一道题：输入一个数组 nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。

比如说，输入一个数组 nums = [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。因为第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。

这道题的暴力解法很好想到，就是对每个元素后面都进行扫描，找到第一个更大的元素就行了。但是暴力解法的时间复杂度是 O(n^2)。

这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「2」的下一个更大元素呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的下一个更大元素，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。

#include <stdio.h>
#include <stdlib.h>

// 定义栈的结构体
struct Stack {
int top;// 栈顶指针
unsigned capacity;  // 栈的容量
int* array; // 存放元素的数组
};

// 创建一个具有指定容量的栈
struct Stack* createStack(unsigned capacity) {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;  // 初始化栈顶指针为-1，表示空栈
stack->array = (int*)malloc(stack->capacity * sizeof(int));  // 为栈数组分配内存
return stack;
}

// 判断栈是否为空
int isStackEmpty(struct Stack* stack) {
return stack->top == -1;  // 栈顶指针为-1表示空栈
}

// 判断栈是否已满
int isStackFull(struct Stack* stack) {
return stack->top == stack->capacity - 1;  // 栈顶指针等于容量减一表示栈已满
}

// 元素入栈
void push(struct Stack* stack, int item) {
if (isStackFull(stack)) {
return;  // 栈满时无法入栈
}
stack->array[++stack->top] = item;  // 栈顶指针加一，将元素放入栈顶
}

// 元素出栈
int pop(struct Stack* stack) {
if (isStackEmpty(stack)) {
return -1;  // 空栈无法出栈，返回-1表示失败
}
return stack->array[stack->top--];  // 返回栈顶元素并将栈顶指针减一
}

// 寻找数组中每个元素的下一个更大元素，并返回结果数组
int* nextGreaterElement(int* nums, int numsSize, int* returnSize) {
int* res = (int*)malloc(numsSize * sizeof(int));  // 分配存放结果的数组内存
struct Stack* stack = createStack(numsSize);  // 创建一个栈
for (int i = numsSize - 1; i >= 0; i--) {
while (!isStackEmpty(stack) && stack->array[stack->top] <= nums[i]) {
pop(stack);  // 弹出栈中较小的元素，直到栈为空或者栈顶元素大于当前元素
}
res[i] = isStackEmpty(stack) ? -1 : stack->array[stack->top];  // 将下一个更大元素存入结果数组
push(stack, nums[i]);  // 当前元素入栈
}
*returnSize = numsSize;  // 设置返回结果的大小
free(stack->array);  // 释放栈数组的内存
free(stack);  // 释放栈的内存
return res;  // 返回结果数组指针
}

int main() {
int nums[] = { 1, 2, 3, 4}; // 示例输入数组,
int numsSize = sizeof(nums) / sizeof(nums[0]);
int returnSize;
int* result = nextGreaterElement(nums, numsSize, &returnSize);  // 调用函数得到结果数组
printf("Next Greater Elements: ");
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);  // 打印结果数组
}
free(result);  // 释放结果数组内存
return 0;
}

这就是单调队列解决问题的模板。for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。while 循环是把两个「个子高」元素之间的元素排除，因为他们的存在没有意义，前面挡着个「更高」的元素，所以他们不可能被作为后续进来的元素的下一个更大元素了。

这个算法的时间复杂度不是那么直观，如果你看到 for 循环嵌套 while 循环，可能认为这个算法的复杂度也是 O(n^2)，但是实际上这个算法的复杂度只有 O(n)。

分析它的时间复杂度，要从整体来看：总共有 n 个元素，每个元素都被 push 入栈了一次，而最多会被 pop 一次，没有任何冗余操作。所以总的计算规模是和元素规模 n 成正比的，也就是 O(n) 的复杂度。

单调队列结构解决滑动窗口问题

cal笔记里有

⼀道数组去重的算法题把我整不会了

关于去重算法，应该没什么难度，往哈希集合里面塞不就行了么？

最多给你加点限制，问你怎么给有序数组原地去重，这个我们前文 双指针技巧秒杀七道数组题目 讲过。

本文讲的问题应该是去重相关算法中难度最大的了，把这个问题搞懂，就再也不用怕数组去重问题了。

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：

输入：s = "bcabc"
输出："abc"
示例 2：

输入：s = "cbacdcbc"
输出："acdb"
提示：

1 <= s.length <= 104

s 由小写英文字母组成

题目的要求总结出来有三点：

要求一、要去重。

要求二、去重字符串中的字符顺序不能打乱 s 中字符出现的相对顺序。

要求三、在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果。

上述三条要求中，要求三可能有点难理解，举个例子。

比如说输入字符串 s = "babc"，去重且符合相对位置的字符串有两个，分别是 "bac" 和 "abc"，但是我们的算法得返回 "abc"，因为它的字典序更小。

按理说，如果我们想要有序的结果，那就得对原字符串排序对吧，但是排序后就不能保证符合 s 中字符出现顺序了，这似乎是矛盾的。

其实这里会借鉴后文 单调栈解题框架 中讲到的「单调栈」的思路，没看过也无妨，等会你就明白了。

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

char* removeDuplicateLetters(char* s) {
int freq[26] = {0}; // 记录每个字符出现的频率
int visited[26] = {false}; // 记录每个字符是否已经访问过
int len = strlen(s);
for (int i = 0; i < len; i++) {
freq[s[i] - 'a']++; // 统计每个字符出现的频率
}
char result[26]; // 存储结果的数组
int index = 0; // 结果数组的下标
for (int i = 0; i < len; i++) {
freq[s[i] - 'a']--; // 每遇到一个字符，将其频率减一
if (visited[s[i] - 'a']) {
continue; // 如果字符已经访问过，则跳过当前循环
}
while (index > 0 && s[i] < result[index - 1] && freq[result[index - 1] - 'a'] > 0) {
visited[result[index - 1] - 'a'] = false; // 将之前的字符标记为未访问过
index--; // 移除之前的字符
}
result[index++] = s[i]; // 将当前字符加入结果数组中
visited[s[i] - 'a'] = true; // 标记当前字符为已访问过
}
result[index] = '\0'; // 添加字符串结束的标记
char* res = strdup(result); // 将结果数组复制到动态分配的内存中
return res;
}

int main() {
char s[] = "cbacdcbc";
char* result = removeDuplicateLetters(s);
printf("Result: %s\n", result);
free(result);
return 0;
}