单调栈

503. 下一个更大元素 II给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。 示例 1: 12345输入: nums = [1,2,1]输出: [2,-1,2]解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。 示例 2: 12输入: nums = [1,2,3,4,3]输出: [2,3,4,-1,4] 解题思路核心思路是单调栈 + 数组翻倍模拟循环，通过将数组复制一份拼接在末尾（模拟循环），利用单调栈高效找到每个元素的下一个更大元素： 模拟循环数组： 将原数组 nums 复制一份并拼接在末尾（如 [1,2,1] 变为...

496. 下一个更大元素 Inums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。 示例 1： 123456输入：nums1 = [4,1,2], nums2 = [1,3,4,2].输出：[-1,3,-1]解释：nums1 中每个值的下一个更大元素如下所述：- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。- 1 ，用加粗斜体标识，nums2 =...

84. 柱状图中最大的矩形给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 示例 1: 123输入：heights = [2,1,5,6,2,3]输出：10解释：最大的矩形为图中红色区域，面积为 10 示例 2： 12输入： heights = [2,4]输出： 4 解题思路该解法是对单调栈思路的优化实现，通过在数组末尾添加哨兵元素和栈初始化技巧，将左右边界的计算合并到一次遍历中，代码更简洁且效率更高。 核心优化思路 哨兵元素（Sentinel）： 在原数组末尾添加 -1（高度为负数的哨兵），确保遍历结束时栈中所有元素都会被弹出计算（相当于 “大火收汁”）； 栈初始时推入 -1（索引哨兵），解决栈空时的边界判断问题，同时自然对应 “左侧无更矮柱子” 的情况（left[i] = -1）。 一次遍历计算左右边界： 遍历每个元素作为右侧边界（right），当当前高度小于栈顶高度时，栈顶元素的左右边界均已确定： 右边界：当前索引...

402. 移掉 K 位数字给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。 示例 1 ： 123输入：num = "1432219", k = 3输出："1219"解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。 示例 2 ： 123输入：num = "10200", k = 1输出："200"解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。 示例 3 ： 123输入：num = "10", k = 2输出："0"解释：从原数字移除所有的数字，剩余为空就是 0 。 解题思路核心思路是单调栈 + 贪心算法，通过维护一个递增的栈来确保剩余数字最小，同时控制移除的数字数量不超过 k： 单调栈逻辑： 遍历字符串中的每个数字，对于当前数字c： 若栈不为空，且栈顶数字大于 c，且仍有可移除的次数（k >...

42. 接雨水给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 123输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 12输入：height = [4,2,0,3,2,5]输出：9 解题思路核心思路是双指针边界，通过每个柱子能接住的雨水量取决于其左右两侧的最高柱子中较矮的那个（短板效应）： 边界定义： 对于位置 i，左侧最高柱子高度为 left_max[i]； 右侧最高柱子高度为 right_max[i]； 位置 i 能接住的雨水量为 min(left_max[i], right_max[i]) - height[i]（若结果为正，否则为 0）。 优化实现： 采用双指针法，无需额外存储 left_max 和 right_max 数组，将空间复杂度降至 O (1)； 用 left 和 right...

316. 去除重复字母给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。 示例 1： 12输入：s = "bcabc"输出："abc" 示例 2： 12输入：s = "cbacdcbc"输出："acdb" 核心思路是单调栈 + 贪心算法，通过维护一个单调递增的栈来确保字典序最小，同时利用计数数组判断字符是否还有剩余，确保每个字符只保留一次： 预处理： 统计字符串中每个字符的出现次数（count 数组）； 记录字符是否已在栈中（in_stack 数组），避免重复添加。 单调栈逻辑： 遍历字符串中的每个字符C： 减少 count[c]（当前字符已被考虑）； 若 c 已在栈中，直接跳过； 若 c 不在栈中，且栈不为空，且栈顶字符大于 c，且栈顶字符在后续还有出现（count[栈顶字符] > 0），则弹出栈顶字符（确保字典序更小）； 将 c...