stack题目type
status
date
slug
summary
tags
category
icon
password
Property
删除字符串中的所有相邻重复项
题目：给出由小写字母组成的字符串
S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。示例：
每日温度
题目：给定一个整数数组
temperatures ，表示每天的温度，返回一个数组answer ，其中answer[i]是指对于第i天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用0来代替。示例：
对于温度列表 ，单调栈 的初始状态为空，答案 的初始状态是，按照以下步骤更新单调栈和答案，其中单调栈内的元素都是下标，括号内的数字表示下标在温度列表中对应的温度。
- 当时，单调栈为空，因此将0进栈。，
- 当时，由于74大于73，因此移除栈顶元素0，赋值，将1进栈，，
- 当时，由于75大于74，因此移除栈顶元素1，赋值，将2进栈， ，
- 当时，由于71小于75，因此将3进栈，，
- 当时，由于69小于71，因此将4进栈，，
- 当时，由于72大于69和71，因此依次移除栈顶元素4和3，赋值 和，将5进栈，，
- 当时，由于76大于72和75，因此依次移除栈顶元素5和2，赋值和，将6进栈，，
- 当 时，由于73小于76，因此将7进栈，，
最小栈
题目：
设计一个支持
push，pop，top操作，并能在常数时间内检索到最小元素的栈，实现 MinStack 类:MinStack()初始化堆栈对象
void push(int val)将元素val推入堆栈
void pop()删除堆栈顶部的元素
int top()获取堆栈顶部的元素
int getMin()获取堆栈中的最小元素
示例：
使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值：
有效的括号
题目：给定一个只包括
'('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例：
当遇到匹配的最小括号对时，我们将这对括号从栈中删除（即出栈），如果最后栈为空，那么它是有效的括号，反之不是。
最长有效括号
题目：给一个只包含
'(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。示例：
- 用栈维护当前待匹配的左括号的位置，同时用
start记录一个新的可能合法的子串的起始位置，初始设为0。
- 如果
s[i] =='('，那么把i进栈。
- 如果
s[i] == ')'，那么弹出栈顶元素 （代表栈顶的左括号匹配到了右括号），出栈后： - 如果栈为空，说明以当前右括号为右端点的合法括号序列的左端点为
start，则更新答案i - start + 1 - 如果栈不为空，说明以当前右括号为右端点的合法括号序列的左端点为栈顶元素的下一个元素，则更新答案
i - st.top()
- 遇到右括号
)且当前栈为空，则当前的start开始的子串不再可能为合法子串了，下一个合法子串的起始位置可能是i + 1，更新tart = i + 1
有效的括号字符串
题目：给一个只包含三种字符的字符串，支持的字符类型分别是
'('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。有效字符串符合如下规则：- 任何左括号
'('必须有相应的右括号')'。
- 任何右括号
')'必须有相应的左括号'('。
- 左括号
'('必须在对应的右括号之前')'。
'*'可以被视为单个右括号')'，或单个左括号'('，或一个空字符串。
- 一个空字符串也被视为有效字符串。
示例：
如果字符串中没有星号，则只需要一个栈存储左括号，在从左到右遍历字符串的过程中检查括号是否匹配。
在有星号的情况下，需要两个栈分别存储左括号和星号。从左到右遍历字符串，进行如下操作。
- 如果遇到左括号，则将当前下标存入左括号栈
- 如果遇到星号，则将当前下标存入星号栈
- 如果遇到右括号，则需要有一个左括号或星号和右括号匹配，由于星号也可以看成右括号或者空字符串，因此当前的右括号应优先和左括号匹配，没有左括号时和星号匹配：
- 如果左括号栈不为空，则从左括号栈弹出栈顶元素；
- 如果左括号栈为空且星号栈不为空，则从星号栈弹出栈顶元素；
- 如果左括号栈和星号栈都为空，则没有字符可以和当前的右括号匹配，返回
遍历结束之后，左括号栈和星号栈可能还有元素。为了将每个左括号匹配，需要将星号看成右括号，且每个左括号必须出现在其匹配的星号之前。当两个栈都不为空时，每次从左括号栈和星号栈分别弹出栈顶元素，对应左括号下标和星号下标，判断是否可以匹配，匹配的条件是左括号下标小于星号下标，如果左括号下标大于星号下标则返回 。
最终判断左括号栈是否为空。如果左括号栈为空，则左括号全部匹配完毕，剩下的星号都可以看成空字符串，此时 是有效的括号字符串，返回 。如果左括号栈不为空，则还有左括号无法匹配，此时不是有效的括号字符串，返回。
字符串解码
题目：给定一个经过编码的字符串，返回它解码后的字符串。编码规则为:
k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。示例：
基本计算器
题目：给一个字符串表达式
s ，请实现一个基本计算器来计算并返回它的值。注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。示例：
使用两个栈
nums（存放所有的数字）和ops （存放所有的数字以外的操作，+/-也看做是一种操作）然后从前往后做，对遍历到的字符做分情况讨论：
- 空格 : 跳过
(: 直接加入ops中，等待与之匹配的 )
): 使用现有的nums和ops进行计算，直到遇到左边最近的一个左括号为止，计算结果放到nums
- 数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums
- +/- : 需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉，使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums
基本计算器 II
题目：
给你一个字符串表达式
s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。可以假设给定的表达式总是有效的。所有中间结果将在 的范围内。注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。示例：
简化路径
题目：
给一个字符串
path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。在 Unix 风格的文件系统中，一个点（
.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。请注意，返回的 规范路径 必须遵循下述格式：
- 始终以斜杠
'/'开头
- 两个目录名之间必须只有一个斜杠
'/'
- 最后一个目录名（如果存在）不能 以
'/'结尾
- 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含
'.'或'..'）。
返回简化后得到的 规范路径 。
示例：
从前向后遍历，如果遇到/ 跳过，遇到其他的字符，记录当前/到下一个/之间的字符串，将得到的字符串判断是否为
".."，如果是，就将temp的末尾删除；如果不是，将字符串存入temp中下一个更大元素 II
题目：给定一个循环数组
nums（ nums[nums.length - 1]的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。数字x的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。示例：
柱状图中最大的矩形
题目：给定
n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。示例：
考察到下一个柱子时，发现其值1小于之前记录的柱子高度2。因此，这时可以确定第一个柱子所能勾勒出的矩形的面积。在确定其面积后，之前的记录中就可以将第一个柱子删除了
接着，对于第二个柱子1来说，同样需要先将其记录下来
然后考察第三个柱子5，这时柱子5的高度大于柱子1的高度。因此，它们所勾勒出的矩形是什么样依旧不能确定，将第三个柱子先记录下来。
继续考察第四个柱子。对于第四个柱子6来说，它的高度大于已经记录的二、三两个柱子的高度。因此，这三个柱子所能勾勒出的矩形面积依旧不能确定，将第四个柱子先做记录。
继续考察第五个柱子。第五个柱子的高度为2，小于其前一个柱子的高度6。因此，到这里，可以确定以6为高的柱子所能勾勒出的矩形面积。
由于，之前记录的柱子高度是逐渐递增的，所以其左侧边界可以确定；同时，由于当前考察的柱子高度为2小于6，所以对于以6为高的柱子来说，其右侧边界也确定了。这样，它所能勾勒出的矩形面积就确定了。之后，将其从记录列表移除就可以。
在以6为高的柱子从记录列表中移除之后，接着可以确定的就是以5为高的柱子所勾勒出的矩形面积。同样的，计算之后，需要将其从列表中移除。
求解的思路是：
- 先将题目给定的数组左右各添加一个元素0，为了方便确定原有数组中第一个元素和最后一个元素能不能继续扩张
- 然后开始从左到右依次遍历数组中的元素：
- 如果栈为空或者当前考察的新元素值比栈顶元素值大，表明以栈顶元素值为高的矩形面积暂不能确定，所以就将当前考察的新元素入栈。在这个条件下，栈中的元素值从栈底到栈顶是依次递增的；
- 如果栈不为空且当前考察的新元素值比栈顶元素值小，表明以栈顶元素值为高的矩形的面积是可以确定的了。该矩形的高就是栈顶元素值，其右侧边界就是当前考察的新元素，左侧边界是栈顶元素的前一个元素，因为，在上一步中知道栈中元素值从栈底到栈顶是依次递增的。 因此，矩形的宽是当前考察的元素索引与栈顶元素前一个元素的索引的差值减一。
这里需要注意的是，当栈顶元素出栈后，需要继续看当前考察的新元素值是否大于新的栈顶元素值，如果是，就继续将栈顶元素弹出，然后计算以其值为高的矩形面积，直到当前考察的新元素值大于栈顶元素值时，当前考察元素入栈。
最后，由于最终计算矩形面积时，是用两个柱子的索引来确定矩形宽度的。因此，栈中存储的应该是给定数组的索引。
最大矩形
题目：给定一个仅包含
0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。示例：
轮询每一行，累加当前列的高度。同时利用单调栈，找到可以计算面积的栈顶元素。