力扣hot100刷题——栈

文章目录 69.有效的括号题目描述思路：栈code 70.最小栈题目描述思路：双栈法code优化：单栈法code 71.字符串解码题目描述思路：栈code 73.每日温度题目描述思路：单调栈code 74.柱状图中最大的矩形题目描述思路：单调栈code

69.有效的括号 题目描述

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

示例 1：

**输入：**s = “()”

**输出：**true

示例 2：

**输入：**s = “()[]{}”

**输出：**true

示例 3：

**输入：**s = “(]”

**输出：**false

示例 4：

**输入：**s = “([])”

**输出：**true

提示：

1 <= s.length <= 10^4s 仅由括号 '()[]{}' 组成 思路：栈 栈的使用： 使用栈来保存未匹配的左括号。遍历字符串，遇到左括号时，将其压入栈中。遇到右括号时，检查栈顶的左括号是否与之匹配： 如果匹配，则将栈顶的左括号弹出。如果不匹配，则说明字符串无效，直接返回 false。 最终检查： 遍历结束后，检查栈是否为空： 如果栈为空，说明所有括号都匹配成功，返回 true。如果栈不为空，说明有未匹配的左括号，返回 false。 code #include <stdbool.h> #include <string.h> bool isValid(char* s) { // 定义一个栈，用于存放未匹配的左括号 char st[10000 + 5]; int size = 0; // 栈的大小 int len = strlen(s); // 字符串的长度 // 遍历字符串中的每一个字符 for (int i = 0; i < len; i++) { // 如果是左括号，压入栈中 if (s[i] == '(' || s[i] == '[' || s[i] == '{') { st[size++] = s[i]; } // 如果是右括号，检查是否与栈顶的左括号匹配 else { // 如果栈为空，说明没有与之匹配的左括号，返回 false if (size == 0) return false; // 获取栈顶的左括号 char top = st[size - 1]; // 检查栈顶的左括号是否与当前的右括号匹配 if ((top == '(' && s[i] == ')') || (top == '[' && s[i] == ']') || (top == '{' && s[i] == '}')) { // 匹配成功，弹出栈顶的左括号 size--; } else { // 匹配失败，返回 false return false; } } } // 遍历结束后，检查栈是否为空 // 如果栈为空，说明所有括号都匹配成功；否则说明有未匹配的左括号 return size == 0; } 70.最小栈 题目描述

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。

示例 1:

输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

提示：

-2^31 <= val <= 2^31 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 10^4 次 思路：双栈法 主栈：用于存储所有元素。辅助栈：用于存储当前栈中的最小值。 每当主栈压入一个元素时，辅助栈也压入当前的最小值。每当主栈弹出一个元素时，辅助栈也弹出栈顶元素。这样，辅助栈的栈顶始终是当前栈中的最小值。

这里的辅助栈相当于一个前缀最小值，记录当前最小值。

code #include <stdio.h> #include <stdlib.h> #include <limits.h> // 定义栈的最大容量 #define MAX_SIZE 10000 // 定义最小栈结构体 typedef struct { int mainStack[MAX_SIZE]; // 主栈，存储所有元素 int minStack[MAX_SIZE]; // 辅助栈，存储当前最小值 int top; // 栈顶指针 } MinStack; // 初始化最小栈 MinStack* minStackCreate() { MinStack* obj = (MinStack*)malloc(sizeof(MinStack)); obj->top = -1; // 初始化栈顶指针为 -1，表示栈为空 return obj; } // 将元素压入栈中 void minStackPush(MinStack* obj, int val) { if (obj->top >= MAX_SIZE - 1) { // 栈已满，无法压入 return; } // 将元素压入主栈 obj->top++; obj->mainStack[obj->top] = val; // 如果辅助栈为空，或者当前值小于等于辅助栈的栈顶元素，则压入辅助栈 if (obj->top == 0 || val <= obj->minStack[obj->top - 1]) { obj->minStack[obj->top] = val; } else { // 否则，将辅助栈的栈顶元素复制到当前位置 obj->minStack[obj->top] = obj->minStack[obj->top - 1]; } } // 弹出栈顶元素 void minStackPop(MinStack* obj) { if (obj->top < 0) { // 栈为空，无法弹出 return; } // 弹出栈顶元素 obj->top--; } // 获取栈顶元素 int minStackTop(MinStack* obj) { if (obj->top < 0) { // 栈为空，返回一个无效值 return INT_MIN; } // 返回主栈的栈顶元素 return obj->mainStack[obj->top]; } // 获取栈中的最小元素 int minStackGetMin(MinStack* obj) { if (obj->top < 0) { // 栈为空，返回一个无效值 return INT_MIN; } // 返回辅助栈的栈顶元素，即当前最小值 return obj->minStack[obj->top]; } // 释放最小栈的内存 void minStackFree(MinStack* obj) { free(obj); } /** * Your MinStack struct will be instantiated and called as such: * MinStack* obj = minStackCreate(); * minStackPush(obj, val); * minStackPop(obj); * int param_3 = minStackTop(obj); * int param_4 = minStackGetMin(obj); * minStackFree(obj); */ 优化：单栈法

栈中存储差值：

栈中存储当前元素与最小值的差值。用一个变量 min 记录当前的最小值。当压入元素时，计算当前元素与 min 的差值，并更新 min。当弹出元素时，根据栈顶的差值恢复 min。 code #include <stdio.h> #include <stdlib.h> #include <limits.h> // 定义栈的最大容量 #define MAX_SIZE 10000 // 定义最小栈结构体 typedef struct { long stack[MAX_SIZE]; // 栈，存储当前值与最小值的差值 int top; // 栈顶指针 long min; // 当前最小值 } MinStack; // 初始化最小栈 MinStack* minStackCreate() { MinStack* obj = (MinStack*)malloc(sizeof(MinStack)); obj->top = -1; // 初始化栈顶指针为 -1，表示栈为空 obj->min = 0; // 初始化最小值为 0 return obj; } // 将元素压入栈中 void minStackPush(MinStack* obj, int val) { if (obj->top >= MAX_SIZE - 1) { // 栈已满，无法压入 return; } if (obj->top == -1) { // 如果栈为空，当前值就是最小值 obj->stack[++obj->top] = 0; // 差值为 0 obj->min = val; } else { // 计算当前值与最小值的差值 long diff = (long)val - obj->min; obj->stack[++obj->top] = diff; // 如果当前值小于最小值，更新最小值 if (diff < 0) { obj->min = val; } } } // 弹出栈顶元素 void minStackPop(MinStack* obj) { if (obj->top < 0) { // 栈为空，无法弹出 return; } // 获取栈顶的差值 long diff = obj->stack[obj->top--]; // 如果差值为负数，说明弹出的是最小值，需要更新 min if (diff < 0) { obj->min = obj->min - diff; } } // 获取栈顶元素 int minStackTop(MinStack* obj) { if (obj->top < 0) { // 栈为空，返回一个无效值 return INT_MIN; } // 如果栈顶的差值非负，则栈顶元素为 min + diff // 如果栈顶的差值为负，则栈顶元素为 min long diff = obj->stack[obj->top]; if (diff >= 0) { return (int)(obj->min + diff); } else { return (int)obj->min; } } // 获取栈中的最小元素 int minStackGetMin(MinStack* obj) { if (obj->top < 0) { // 栈为空，返回一个无效值 return INT_MIN; } // 直接返回 min return (int)obj->min; } void minStackFree(MinStack* obj) { free(obj); } /** * Your MinStack struct will be instantiated and called as such: * MinStack* obj = minStackCreate(); * minStackPush(obj, val); * minStackPop(obj); * int param_3 = minStackTop(obj); * int param_4 = minStackGetMin(obj); * minStackFree(obj); */ 71.字符串解码 题目描述

394. 字符串解码

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

编码规则为: 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 <= 30s 由小写英文字母、数字和方括号 '[]' 组成s 保证是一个 有效 的输入。s 中所有整数的取值范围为 [1, 300] 思路：栈 栈： 使用一个 数字栈 来存储重复次数。使用一个 字符栈 来存储字符（包括字母和左括号）。 遍历字符串： 如果遇到数字，解析完整的数字并压入数字栈。如果遇到左括号 [ 或字母，直接压入字符栈。如果遇到右括号 ]，开始解码： 弹出数字栈顶的重复次数。弹出字符栈中的字符，直到遇到左括号 [。将弹出的字符重复指定次数，并重新压入字符栈。 code #include <stdio.h> #include <stdlib.h> #include <string.h> char* decodeString(char* s) { int numStack[30]; // 数字栈，用于存储重复次数 int numtop = 0; // 数字栈的栈顶指针 char* charStack = malloc(sizeof(char) * 9001); // 字符栈，用于存储字符 int chartop = 0; // 字符栈的栈顶指针 char* tempStack = malloc(sizeof(char) * 9001); // 临时栈，用于存储需要重复的字符 int temptop = 0; // 临时栈的栈顶指针 int i = 0; // 遍历字符串的索引 while (s[i] != '\0') { if (s[i] >= '0' && s[i] <= '9') { // 解析数字 int cnt = s[i++] - '0'; // 将字符转换为数字 while (s[i] >= '0' && s[i] <= '9') { cnt = cnt * 10 + (s[i] - '0'); // 处理多位数 i++; } numStack[numtop++] = cnt; // 将数字压入数字栈 } else if (s[i] == ']') { // 遇到右括号，开始解码 int cnt = numStack[--numtop]; // 弹出数字栈顶的重复次数 int t = chartop; // 找到字符栈中最近的左括号 while (charStack[--t] != '['); // 将左括号和右括号之间的字符复制到临时栈 temptop = 0; for (int j = t + 1; j < chartop; j++) { tempStack[temptop++] = charStack[j]; } // 弹出字符栈中的左括号 chartop = t; // 将临时栈中的字符重复 cnt 次，并压回字符栈 for (int j = 0; j < cnt; j++) { for (int k = 0; k < temptop; k++) { charStack[chartop++] = tempStack[k]; } } i++; // 移动到下一个字符 } else { // 普通字符或左括号，直接压入字符栈 charStack[chartop++] = s[i++]; } } // 在字符栈末尾添加字符串结束符 charStack[chartop] = '\0'; // 释放临时栈的内存 free(tempStack); return charStack; } 73.每日温度 题目描述

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90] 输出: [1,1,0]

提示：

1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100 思路：单调栈

维护一个单调不增的栈（栈底代表的元素大于栈顶代表的元素）：

由于本题需要计算天数差值，因此栈中保存的是数组下标。

遍历温度数组：

当前元素小于栈顶对应的元素或栈为空时，温度数组的下标入栈当前元素大于栈顶对应的元素时，栈顶元素出栈并计算下标差值，写入答案数组的对应位置，继续比较，直到当前元素小于栈顶对应的元素或栈为空，将该下表入栈。

若最后栈不为空，说明在其后没有找到值更大的元素，将栈中元素对应答案数组的位置全部置为0。

code #include <stdio.h> #include <stdlib.h> int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) { *returnSize = temperaturesSize; // 设置返回数组的大小 int* ans = malloc(sizeof(int) * temperaturesSize); // 分配结果数组的内存 int st[temperaturesSize]; // 单调栈，用于存储温度的下标 int top = 0; // 栈顶指针，初始值为 0 // 维护一个单调不增的栈 // 规则： // 1. 当前元素小于等于栈顶元素：当前元素的下标入栈 // 2. 当前元素大于栈顶元素：计算栈顶元素的下标差值，栈顶出栈，继续比较 for (int i = 0; i < temperaturesSize; i++) { if (top == 0 || temperatures[i] <= temperatures[st[top - 1]]) { // 如果栈为空，或者当前温度小于等于栈顶温度，当前下标入栈 st[top++] = i; } else { // 如果当前温度大于栈顶温度 while (top > 0 && temperatures[i] > temperatures[st[top - 1]]) { // 计算栈顶元素对应的等待天数 ans[st[top - 1]] = i - st[top - 1]; // 栈顶元素出栈 top--; } // 当前下标入栈 st[top++] = i; } } // 处理栈中剩余的元素 // 这些元素表示没有更高的温度，等待天数为 0 while (top > 0) { ans[st[--top]] = 0; } // 返回结果数组 return ans; } 74.柱状图中最大的矩形 题目描述

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： heights = [2,4] 输出： 4

提示：

1 <= heights.length <=10^50 <= heights[i] <= 10^4 思路：单调栈 初始化一个栈 stack 和一个变量 maxArea，用于记录最大面积。遍历 heights 数组： 对于当前柱子 heights[i]，检查栈顶元素： 如果栈不为空且当前柱子高度小于栈顶元素对应的柱子高度，说明找到了右边界。弹出栈顶元素，并计算以该柱子为高度的矩形面积： 宽度 = 当前下标 i - 栈顶元素下标 stack[top - 1] - 1。面积 = 高度 heights[stack[top]] * 宽度。 更新 maxArea。重复上述过程，直到栈为空或当前柱子高度不小于栈顶元素对应的柱子高度。 将当前下标 i 压入栈中。 遍历结束后，处理栈中剩余的元素： 弹出栈顶元素，并计算以该柱子为高度的矩形面积： 宽度 = 数组长度 n - 栈顶元素下标 stack[top - 1] - 1。面积 = 高度 heights[stack[top]] * 宽度。更新 maxArea。 返回 maxArea。 code #include <stdio.h> #include <stdlib.h> int largestRectangleArea(int* heights, int heightsSize) { int* stack = malloc(sizeof(int) * (heightsSize + 1)); // 单调栈，存储柱子的下标 int top = -1; // 栈顶指针 int maxArea = 0; // 最大面积 // 遍历柱子数组 for (int i = 0; i <= heightsSize; i++) { // 当前柱子的高度（如果是最后一个柱子，高度为 0） int h = (i == heightsSize) ? 0 : heights[i]; // 如果栈不为空且当前柱子高度小于栈顶元素对应的柱子高度 while (top != -1 && h < heights[stack[top]]) { int height = heights[stack[top--]]; // 弹出栈顶元素 int width = (top == -1) ? i : i - stack[top] - 1; // 计算宽度 int area = height * width; // 计算面积 if (area > maxArea) { maxArea = area; // 更新最大面积 } } // 将当前下标压入栈中 stack[++top] = i; } // 释放栈的内存 free(stack); return maxArea; }