𝒞𝒶𝓃𝒶𝓇𝓎

题目描述给你一个数组 prices，其中 prices[i] 是商店里第 i 件商品的价格。商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的最小下标，如果没有满足条件的 j，你将没有任何折扣。请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。 例如：prices = [8,4,6,2,3]，输出 [4,2,4,2,3]。 解释：商品 0 价格 8，右侧第一个 <= 8 的是价格 4，最终支付 8-4=4；商品 1 价格 4，右侧第一个 <= 4 的是价格 2，最终支付 4-2=2；商品 2 价格 6，右侧第一个 <= 6 的是价格 2，最终支付 6-2=4；商品 3 价格 2，右侧无 <= 2 的元素，最终支付 2；商品 4 价格 3，右侧无元素，最终支付 3。 解题思路暴力法对每个元素，向右侧扫描寻找第一个不大...

题目描述根据逆波兰表示法（Reverse Polish Notation，RPN），求表达式的值。有效的算符包括 +、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。 解题思路逆波兰表达式是一种后缀表达式，其特点是将运算符放在操作数之后。计算逆波兰表达式非常适合使用栈数据结构。 核心思路：遍历 tokens 数组中的每一个字符串： 如果当前字符串是数字（操作数），直接将其转换为整数并入栈。 如果当前字符串是运算符（+、-、*、/），则从栈中弹出两个操作数（注意弹出顺序：先弹出的是第二个操作数 num2，后弹出的是第一个操作数 num1），根据运算符执行相应的计算，并将计算结果压回栈中。 当遍历完所有 token 后，栈中剩下的唯一一个元素就是整个表达式的计算结果。 关键细节： 由于减法和除法不满足交换律，操作数的顺序很重要。在逆波兰表达式中，遇到运算符时，栈顶元素是右操作数，次栈顶元素是左操作数。例如对于 ["4", "3", "-&...

题目描述给你一个长度为 n 的整数数组 nums。请你构建一个长度为 2n 的答案数组 ans，ans 由两个 nums 数组串联形成。ans[i] == nums[i] 且 ans[i + n] == nums[i]。 例如：nums = [1,2,1]，输出 [1,2,1,1,2,1]。 解释：数组 ans 由两个 [1,2,1] 串联组成。 解题思路核心思想这是一个非常直接的数组操作问题，本质上是将原数组复制两遍拼接到一起。具体做法是： 创建一个长度为 2n 的新数组 ans。 遍历原数组，将每个元素 nums[i] 分别放到 ans[i] 和 ans[i + n] 两个位置。 一次遍历即可完成。 步骤 ans = new int[nums.length * 2] 对于 i 从 0 到 nums.length - 1： ans[i] = nums[i] ans[i + nums.length] = nums[i] 返回 ans。 示例说明以 nums = [1,2,1] 为例： n = 3，ans 长度为 6 i=0：ans[0]=...

问题描述给你一个含 n 个整数的数组 nums，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。 解题思路本题的核心难点在于要求 O(n) 时间复杂度和 O(1) 额外空间（返回列表不计入额外空间）。常规的哈希表做法需要 O(n) 空间，不符合要求。 原地哈希（标记法）元素的值范围是 [1, n]，恰好对应数组索引 [0, n-1]。利用这个特性，我们可以在原数组上进行”标记”： 第一次遍历 —— 标记出现过数字对应的索引： 对于每个元素 nums[i]，取其绝对值得到原值 val 计算索引 index = val - 1 将 nums[index] 变为负数（取反），表示”数字 val 已经出现过” 注意使用 Math.abs() 取绝对值，因为元素可能已经被之前的标记操作变成了负数 第二次遍历 —— 收集缺失的数字： 遍历数组，如果 nums[i] > 0（仍为正数），说明数字 i + 1 没有出现过 将所有正数位置的索引 + 1 收集到结果列表中 举例说明以输...

问题描述给定一个二进制数组 nums，计算其中最大连续 1 的个数。 解题思路本题是经典的遍历 + 计数器问题，思路直接但需要注意边界处理。 单指针遍历法使用两个变量： pre_sum：当前连续 1 的计数 max_sum：全局最大连续 1 的个数 遍历数组： 遇到 1：pre_sum 加 1（或加 num 本身，因为 1 的值为 1） 遇到 0： 用 max_sum = Math.max(max_sum, pre_sum) 更新全局最大值 将 pre_sum 重置为 0（连续被打断） 遍历结束后，再次比较 max_sum 和 pre_sum，因为数组可能以 1 结尾而没有遇到 0 来触发更新 举例说明以输入 nums = [1, 1, 0, 1, 1, 1] 为例： i num pre_sum max_sum 说明 0 1 1 0 遇到 1，计数增加 1 1 2 0 遇到 1，计数增加 2 0 0 2 遇到 0，更新 max_sum=2，重置 pre_sum 3 1 1 2 遇到 1，计数增加 4 1 2 2 遇到 1，计数增加...

题目描述有一个单线程 CPU 正在运行一个含有 n 道函数的程序。每道函数都有一个位于 [0, n-1] 的唯一标识符。 函数调用存储在一个调用栈上：当一个函数调用开始时，它的标识符将会推入栈中。而当一个函数调用结束时，它的标识符将会从栈中弹出。标识符位于栈顶的函数是当前正在执行的函数。 每当一个函数开始或者结束时，将会记录一条日志，包括函数标识符、是开始还是结束、以及相应的时间戳。给你一个由日志组成的列表 logs，请你返回每个函数的独占时间。 每条日志的格式为 "function_id:start|end:timestamp"，其中 timestamp 是一个非负整数，表示函数开始或结束的时间点。注意，同一个函数可能会被递归调用多次。 “独占时间” 是指该函数在 CPU 上执行的所有时间片段之和，不包括它调用其他函数所花费的时间。 解题思路本题的核心是模拟调用栈来跟踪当前正在执行的函数，并记录每个时间片段归谁所有。 关键点：时间片的含义时间戳表示某个时刻，函数从 timestamp 开始执行，或恰好在 timestamp 结束。举例来说： 0:start...

题目描述集合 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 是弹出后新的栈顶），计算面积并更新最大值。 重复上述过程，直到栈顶柱子高度不大于当前柱子，然后将当前柱子下标入栈。 单调栈的本质：栈中始终保持着高度递增的柱子序列...