数据结构与算法-栈
数据结构与算法-栈
栈(Stack)——后进先出(Last in First Out)
LeetCode20.有效的括号
题目
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
1 |
|
示例 2:
1 |
|
示例 3:
1 |
|
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/valid-parentheses
解题
TypeScript
1 |
|
LeetCode503.下一个更大元素 II
题目
给定一个循环数组nums
(nums[nums.length - 1]
的下一个元素是nums[0]
),返回nums
中每个元素的 下一个更大元素 。
数字 x
的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1
。
示例 1:
1 |
|
示例 2:
1 |
|
提示:
1 <= nums.length <= 104
-109 <= nums[i] <= 109
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/next-greater-element-ii
解题
TypeScript
单调栈 + 循环数组
思路及算法
我们可以使用单调栈解决本题。单调栈中保存的是下标,从栈底到栈顶的下标在数组 nums
中对应的值是单调不升的。
每次我们移动到数组中的一个新的位置 i
,我们就将当前单调栈中所有对应值小于 nums
的下标弹出单调栈,这些值的下一个更大元素即为 nums[i]
(证明很简单:如果有更靠前的更大元素,那么这些位置将被提前弹出栈)。随后我们将位置 i
入栈。
但是注意到只遍历一次序列是不够的,例如序列 [2,3,1]
,最后单调栈中将剩余 [3,1]
,其中元素 [1]
的下一个更大元素还是不知道的。
一个朴素的思想是,我们可以把这个循环数组「拉直」,即复制该序列的前 n−1
个元素拼接在原序列的后面。这样我们就可以将这个新序列当作普通序列,用上文的方法来处理。
而在本题中,我们不需要显性地将该循环数组「拉直」,而只需要在处理时对下标取模即可。
1 |
|
其他方式:
1 |
|