一、下一个更大元素1
题目:
nums1
中数字 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:
输入:nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出:[-1,3,-1] 解释:nums1 中每个值的下一个更大元素如下所述: - 4 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。 - 1 ,用加粗斜体标识,nums2 = [1,3,4,2]。下一个更大元素是 3 。 - 2 ,用加粗斜体标识,nums2 = [1,3,4,2]。不存在下一个更大元素,所以答案是 -1 。
示例 2:
输入:nums1 = [2,4], nums2 = [1,2,3,4]. 输出:[3,-1] 解释:nums1 中每个值的下一个更大元素如下所述: - 2 ,用加粗斜体标识,nums2 = [1,2,3,4]。下一个更大元素是 3 。 - 4 ,用加粗斜体标识,nums2 = [1,2,3,4]。不存在下一个更大元素,所以答案是 -1 。
思路:
解法有许多种,这里采用单调栈和哈希表的解法,将数组nums1中的元素和索引全部存入哈希表中,遍历数组nums2,如果栈顶元素小于遍历到的元素,弹出该元素并与map比较有无相同元素,如果有则更新下标为对应的位置
代码:
public int[] nextGreaterElement(int[] nums1, int[] nums2) {// 创建一个哈希表,用于存储 nums1 中每个元素及其索引HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums1.length; i++) {map.put(nums1[i], i);}// 创建结果数组,初始化为 -1int[] res = new int[nums1.length];Arrays.fill(res, -1);// 使用栈来跟踪 nums2 中的元素Stack<Integer> stack = new Stack<>();// 遍历 nums2for (int i = 0; i < nums2.length; i++) {// 当栈不为空且栈顶元素小于当前元素时while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {// 弹出栈顶元素,并更新结果数组int pre = nums2[stack.pop()];// 如果弹出的元素存在于 nums1 中if (map.containsKey(pre)) {res[map.get(pre)] = nums2[i];}}// 将当前元素的索引压入栈中stack.push(i);}return res;
}
这个哈希表用于存储 nums1
中每个元素及其对应的索引位置,以便快速查找。
遍历 nums1
,将每个元素及其索引添加到哈希表中。
创建一个与 nums1
长度相同的结果数组 res
,并用 -1
初始化,表示默认情况下每个元素的下一个更大元素是 -1
。
使用栈来存储 nums2
中的索引,以帮助跟踪当前元素和候选更大元素的比较。
如果栈不为空且栈顶元素小于当前元素,则弹出栈顶元素,检查它是否在 nums1
中。如果是,则更新结果数组中的对应位置。
将当前元素的索引压入栈中,以便后续元素可以用来比较。
暴力解法
public int[] nextGreaterElement(int[] nums1, int[] nums2) {// 创建一个与 nums1 长度相同的结果数组 ans,初始值为 -1int[] ans = new int[nums1.length];for (int i = 0; i < ans.length; i++) {ans[i] = -1; // 默认情况下,所有结果初始化为 -1}// 遍历 nums1 中的每个元素for (int i = 0; i < nums1.length; i++) {int num = nums1[i]; // 当前要寻找下一个更大元素的数字// 遍历 nums2 来寻找 num 的下一个更大元素for (int j = 0; j < nums2.length; j++) {// 找到 num 在 nums2 中的位置if (nums2[j] == num) {int k = j + 1; // 从 num 的下一个位置开始查找// 遍历 nums2 中 num 之后的元素while (k < nums2.length) {// 如果找到比 num 更大的元素if (nums2[k] > num) {ans[i] = nums2[k]; // 更新结果数组break; // 找到下一个更大元素后退出循环}k++; // 否则继续查找}break; // 找到 num 后退出内层循环}}}return ans; // 返回结果数组
}
二、下一个更大元素2
题目:
给定一个循环数组 nums
( nums[nums.length - 1]
的下一个元素是 nums[0]
),返回 nums
中每个元素的 下一个更大元素 。
数字 x
的 下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1
。
示例 1:
输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2; 数字 2 找不到下一个更大的数; 第二个 1 的下一个最大的数需要循环搜索,结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3] 输出: [2,3,4,-1,4]
思路:
本题的特点是数组是一个环形结构,数组中最后一个数的值需要由第二次遍历数组来确定,因此可以将数组进行复制拉长,同时超出数组长度的下标索引采用取模的方法进行定位
代码:
public int[] nextGreaterElements(int[] nums) {// 边界判断:如果 nums 为空或长度小于等于1,直接返回 -1if (nums == null || nums.length <= 1) {return new int[] { -1 };}int size = nums.length; // 数组的长度int[] result = new int[size]; // 结果数组,存放每个元素的下一个更大元素Arrays.fill(result, -1); // 初始化结果数组为 -1,表示默认没有找到更大的元素Stack<Integer> st = new Stack<>(); // 栈,用于存放 nums 数组的下标// 遍历数组 nums 两遍以处理循环的情况for (int i = 0; i < 2 * size; i++) {// 栈不为空且当前元素大于栈顶元素对应的元素while (!st.empty() && nums[i % size] > nums[st.peek()]) {result[st.peek()] = nums[i % size]; // 更新结果数组st.pop(); // 弹出栈顶元素}st.push(i % size); // 将当前元素的下标入栈}return result; // 返回结果数组
}
如果输入数组 nums
为 null
或者数组长度小于等于 1,直接返回一个结果数组 [-1]
。因为对于空数组或单元素数组来说,不可能存在下一个更大的元素。
size
存储数组 nums
的长度。result
数组用于存储每个元素的下一个更大元素,初始时用 -1
表示默认没有找到更大的元素。st
是一个栈,用于存储 nums
中元素的下标。
通过遍历 2 * size
的范围来处理循环的情况。这种方法确保每个元素在循环后的数组中都有机会被检查一次。
nums[i % size]
使用模运算来处理数组的循环性质。
当栈不为空且当前元素 nums[i % size]
大于栈顶元素对应的值时,更新 result
数组,并将栈顶元素弹出。
将当前元素的下标入栈,以便后续可以找到比它大的元素。
返回存储了每个元素下一个更大元素的结果数组。
栈中元素的动态分析
以例子
输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2; 数字 2 找不到下一个更大的数; 第二个 1 的下一个最大的数需要循环搜索,结果也是 2。初始化
- 输入数组
nums = [1,2,1]
- 结果数组
result = [-1, -1, -1]
(初始状态,所有值为-1
)- 栈
st
为空遍历过程
我们遍历
2 * size
次,其中size
是nums
的长度。对于输入nums = [1,2,1]
,size
为3
,因此我们遍历6
次(从0
到5
)。第 1 次迭代(i = 0)
- 当前元素是
nums[0 % 3] = nums[0] = 1
- 栈为空,因此我们将
0
压入栈- 栈状态:
[0]
第 2 次迭代(i = 1)
- 当前元素是
nums[1 % 3] = nums[1] = 2
- 栈不为空,且
2 > nums[st.peek()] = nums[0] = 1
- 更新
result[0] = 2
(栈顶元素的下一个更大元素是2
)- 弹出栈顶元素
0
- 将
1
压入栈- 栈状态:
[1]
- 结果数组:
[2, -1, -1]
第 3 次迭代(i = 2)
- 当前元素是
nums[2 % 3] = nums[2] = 1
- 栈不为空,且
1
不大于nums[st.peek()] = nums[1] = 2
- 将
2
压入栈- 栈状态:
[1, 2]
- 结果数组:
[2, -1, -1]
第 4 次迭代(i = 3)
- 当前元素是
nums[3 % 3] = nums[0] = 1
- 栈不为空,且
1
不大于nums[st.peek()] = nums[2] = 1
- 将
3 % 3 = 0
压入栈- 栈状态:
[1, 2, 0]
- 结果数组:
[2, -1, -1]
第 5 次迭代(i = 4)
- 当前元素是
nums[4 % 3] = nums[1] = 2
- 栈不为空,且
2 > nums[st.peek()] = nums[0] = 1
- 更新
result[0] = 2
(栈顶元素的下一个更大元素是2
)- 弹出栈顶元素
0
- 栈不为空,且
2 > nums[st.peek()] = nums[2] = 1
- 更新
result[2] = 2
(栈顶元素的下一个更大元素是2
)- 弹出栈顶元素
2
- 将
4 % 3 = 1
压入栈- 栈状态:
[1]
- 结果数组:
[2, -1, 2]
第 6 次迭代(i = 5)
- 当前元素是
nums[5 % 3] = nums[2] = 1
- 栈不为空,且
1
不大于nums[st.peek()] = nums[1] = 2
- 将
5 % 3 = 2
压入栈- 栈状态:
[1, 2]
- 结果数组:
[2, -1, 2]
总结
最终得到的结果数组是
[2, -1, 2]
,每个位置对应的下一个更大元素为:
- 对于
nums[0] = 1
,下一个更大的元素是2
- 对于
nums[1] = 2
,在循环数组中没有更大的元素,因此结果是-1
- 对于
nums[2] = 1
,下一个更大的元素是2
三、柱状图中最大的矩形
题目:
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4] 输出: 4
思路:
与接雨水类似,同时处理两边的元素,需要注意的是,题目中为了边界的处理需要对数组进行扩容操作
代码:
public int largestRectangleArea(int[] heights) {Stack<Integer> st = new Stack<Integer>(); // 用于存储直方图的柱子下标// 数组扩容,在头和尾各加入一个高度为0的元素int[] newHeights = new int[heights.length + 2];newHeights[0] = 0; // 头部填充0newHeights[newHeights.length - 1] = 0; // 尾部填充0for (int index = 0; index < heights.length; index++) {newHeights[index + 1] = heights[index]; // 复制原数组到扩容后的数组}heights = newHeights; // 更新原数组为扩容后的数组st.push(0); // 初始将第一个填充的0的下标压入栈int result = 0; // 记录最大的矩形面积// 从第二个元素开始遍历(实际的第一个元素是新数组中的1)for (int i = 1; i < heights.length; i++) {// 比较当前柱子的高度与栈顶柱子的高度if (heights[i] > heights[st.peek()]) {st.push(i); // 当前柱子比栈顶柱子高,直接压栈} else if (heights[i] == heights[st.peek()]) {st.pop(); // 当前柱子与栈顶柱子高度相等,弹出栈顶,重新压栈st.push(i);} else {// 当前柱子低于栈顶柱子,弹出栈顶柱子,计算以弹出的柱子为高度的矩形面积while (heights[i] < heights[st.peek()]) {int mid = st.peek(); // 弹出的柱子下标st.pop();int left = st.peek(); // 弹出柱子左边最近的柱子下标int right = i; // 当前柱子下标int w = right - left - 1; // 宽度为右下标 - 左下标 - 1int h = heights[mid]; // 高度为弹出的柱子的高度result = Math.max(result, w * h); // 更新最大矩形面积}st.push(i); // 压入当前柱子的下标}}return result; // 返回最大矩形面积
}
- 数组扩容:在原数组的两端各加一个高度为0的柱子,简化处理边界情况。
- 栈的作用:用栈来保存柱子的下标,保证栈中柱子的高度是递增的。
- 面积计算:当发现当前柱子高度小于栈顶柱子的高度时,弹出栈顶柱子,并计算以该柱子为高度的矩形面积。
- 更新最大面积:每次计算出的矩形面积都与当前最大值比较,保持最大面积。
栈中元素的动态分析
以例子
输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的矩形为图中红色区域,面积为 10
初始化:
- 扩容后的数组:
[0, 2, 1, 5, 6, 2, 3, 0]
- 栈:
[0]
(索引0的0)遍历开始:
i=1:
heights[1] = 2
2 > 0
(栈顶0),压栈。- 栈:
[0, 1]
i=2:
heights[2] = 1
1 < 2
(栈顶1),弹出栈顶1,计算面积。
- 高度:
2
- 左边界:
0
,右边界:2
- 宽度:
2 - 0 - 1 = 1
- 面积:
2 * 1 = 2
- 继续弹出,
0
的矩形高度为0
,面积为0
,不更新结果。1
压栈。- 栈:
[0, 2]
i=3:
heights[3] = 5
5 > 1
(栈顶2),压栈。- 栈:
[0, 2, 3]
i=4:
heights[4] = 6
6 > 5
(栈顶3),压栈。- 栈:
[0, 2, 3, 4]
i=5:
heights[5] = 2
2 < 6
(栈顶4),弹出栈顶4,计算面积。
- 高度:
6
- 左边界:
3
,右边界:5
- 宽度:
5 - 3 - 1 = 1
- 面积:
6 * 1 = 6
2 < 5
(栈顶3),弹出栈顶3,计算面积。
- 高度:
5
- 左边界:
2
,右边界:5
- 宽度:
5 - 2 - 1 = 2
- 面积:
5 * 2 = 10
- 继续弹出,
2
的矩形高度为1
,面积1 * 1 = 1
,不更新结果。2
压栈。- 栈:
[0, 2, 5]
i=6:
heights[6] = 3
3 > 2
(栈顶5),压栈。- 栈:
[0, 2, 5, 6]
i=7:
heights[7] = 0
0 < 3
(栈顶6),弹出栈顶6,计算面积。
- 高度:
3
- 左边界:
5
,右边界:7
- 宽度:
7 - 5 - 1 = 1
- 面积:
3 * 1 = 3
0 < 2
(栈顶5),弹出栈顶5,计算面积。
- 高度:
2
- 左边界:
2
,右边界:7
- 宽度:
7 - 2 - 1 = 4
- 面积:
2 * 4 = 8
- 继续弹出,
0
的矩形高度为0
,面积为0
,不更新结果。0
压栈。- 栈:
[7]
最终结果:最大矩形面积为10。
总结:栈中的元素是柱子的索引,保持柱子的高度递增。每次遇到较小的柱子时,弹出栈顶,计算相应的矩形面积,并更新最大面积。
今天的学习就到这里