力扣hot100刷题——栈

69.有效的括号

题目描述

20. 有效的括号

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

有效字符串需满足：

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

示例 1：

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

**输出：**true

示例 2：

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

**输出：**true

示例 3：

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

**输出：**false

示例 4：

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

**输出：**true

提示：

• 1 <= s.length <= 10^4
• s 仅由括号 '()[]{}' 组成

思路：栈

1. 栈的使用：
   • 使用栈来保存未匹配的左括号。
   • 遍历字符串，遇到左括号时，将其压入栈中。
   • 遇到右括号时，检查栈顶的左括号是否与之匹配：
     • 如果匹配，则将栈顶的左括号弹出。
     • 如果不匹配，则说明字符串无效，直接返回 false。
2. 最终检查：
   • 遍历结束后，检查栈是否为空：
     • 如果栈为空，说明所有括号都匹配成功，返回 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 {// 如果栈为空，说明没有与之匹配的左括号，返回 falseif (size == 0) return false;// 获取栈顶的左括号char top = st[size - 1];// 检查栈顶的左括号是否与当前的右括号匹配if ((top == '(' && s[i] == ')') || (top == '[' && s[i] == ']') || (top == '{' && s[i] == '}')) {// 匹配成功，弹出栈顶的左括号size--;} else {// 匹配失败，返回 falsereturn 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 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 10^4 次

思路：双栈法

1. 主栈：用于存储所有元素。
2. 辅助栈：用于存储当前栈中的最小值。
   • 每当主栈压入一个元素时，辅助栈也压入当前的最小值。
   • 每当主栈弹出一个元素时，辅助栈也弹出栈顶元素。
   • 这样，辅助栈的栈顶始终是当前栈中的最小值。

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

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;  // 初始化最小值为 0return obj;
}// 将元素压入栈中
void minStackPush(MinStack* obj, int val) {if (obj->top >= MAX_SIZE - 1) {// 栈已满，无法压入return;}if (obj->top == -1) {// 如果栈为空，当前值就是最小值obj->stack[++obj->top] = 0; // 差值为 0obj->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--];// 如果差值为负数，说明弹出的是最小值，需要更新 minif (diff < 0) {obj->min = obj->min - diff;}
}// 获取栈顶元素
int minStackTop(MinStack* obj) {if (obj->top < 0) {// 栈为空，返回一个无效值return INT_MIN;}// 如果栈顶的差值非负，则栈顶元素为 min + diff// 如果栈顶的差值为负，则栈顶元素为 minlong 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;}// 直接返回 minreturn (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 <= 30
• s 由小写英文字母、数字和方括号 '[]' 组成
• s 保证是一个 有效 的输入。
• s 中所有整数的取值范围为 [1, 300]

思路：栈

1. 栈：
   • 使用一个 数字栈 来存储重复次数。
   • 使用一个 字符栈 来存储字符（包括字母和左括号）。
2. 遍历字符串：
   • 如果遇到数字，解析完整的数字并压入数字栈。
   • 如果遇到左括号 [ 或字母，直接压入字符栈。
   • 如果遇到右括号 ]，开始解码：
     • 弹出数字栈顶的重复次数。
     • 弹出字符栈中的字符，直到遇到左括号 [。
     • 将弹出的字符重复指定次数，并重新压入字符栈。

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^5
• 30 <= 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;}}// 处理栈中剩余的元素// 这些元素表示没有更高的温度，等待天数为 0while (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^5
• 0 <= 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;
}