𝒞𝒶𝓃𝒶𝓇𝓎

题目描述集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。 给定一个数组 nums 代表了该集合发生错误后的结果。找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。 示例：输入 nums = [1,2,2,4]，输出 [2,3]。其中 2 是重复的数字，3 是丢失的数字。 解题思路本题本质上是在 1 到 n 这 n 个数字中，有一个数字出现了两次，有一个数字没有出现。我们需要找出这两个数字。 方法：计数数组因为数组中的数字都在 [1, n] 范围内，我们可以使用一个长度为 n 的辅助数组（或直接在原数组上标记）来统计每个数字出现的次数。 创建一个长度为 n 的数组 res，初始值全为 0。 遍历 nums，对于每个数字 num，将 res[num - 1] 的值加 1。 再次遍历 res（或遍历 1 到 n）： 如果 res[i] == 0，说明数字 i + 1 没有出现过，即丢失的数字。 如果 res[i] == 2，说明数字 i + 1 出现了两次，即...

题目描述给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 例如：temperatures = [73,74,75,71,69,72,76,73]，输出 [1,1,4,2,1,1,0,0]。 解释：第 0 天温度 73，下一天（第 1 天）温度 74 > 73，所以 answer[0] = 1；第 2 天温度 75，4 天后（第 6 天）温度 76 > 75，所以 answer[2] = 4。 解题思路本题是经典的单调栈问题——更具体地说，是单调递减栈的应用，用来寻找每个元素右侧第一个比它大的元素的距离。 暴力解法对于每一天，向后扫描直到找到更高的温度，时间复杂度为 O(n^2)。当 n = 10^5 时会超时。 单调栈解法核心思想：维护一个从栈底到栈顶递减（指温度值）的栈，栈中存储的是下标而非温度值。 遍历温度数组，对于每一天 i： 当栈不为空，且当前温度 temperatures[i] 大于栈顶下标...

题目描述给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。求在该柱状图中，能够勾勒出来的矩形的最大面积。 解题思路本题要求计算柱状图中能勾勒出的最大矩形面积，是单调栈的经典应用。 核心思路是：对于每一根柱子，如果我们以它的高度作为矩形的高，那么我们需要找到它左右两边第一个比它矮的柱子，这两个柱子之间的宽度就是该矩形可以扩展的最大宽度。 单调栈解法： 预处理：在原数组的首尾各添加一个高度为 0 的哨兵柱子。这样做的好处是： 头部哨兵确保栈永远不会为空（stack.peek() 始终有效） 尾部哨兵确保遍历结束后，栈中所有柱子都会出栈计算面积 维护单调递增栈：栈中存储的是下标，对应的高度值单调递增。遍历每个柱子 i： 当当前柱子的高度小于栈顶柱子的高度时，说明栈顶柱子的”右边界”已经找到了。弹出栈顶，以该柱子的高度作为矩形高，宽度为 i - left - 1（其中 left 是弹出后新的栈顶），计算面积并更新最大值。 重复上述过程，直到栈顶柱子高度不大于当前柱子，然后将当前柱子下标入栈。 单调栈的本质：栈中始终保持着高度递增的柱子序列...