文章目录
- day59学习内容
- 一、下一个更大元素II
- 1.1、思路
- 1.2、代码
- 二、接雨水
- 2.1、双指针法
- 2.1.1、思路
- 2.1.2、代码
- 2.2、单调栈法
- 2.2.1、思路
- 2.2.2、代码
- 总结
- 1.感想
- 2.思维导图
day59学习内容
day59主要内容
- 下一个更大元素II
- 接雨水
声明
本文思路和文字,引用自《代码随想录》
一、下一个更大元素II
503.原题链接
1.1、思路
-
数组的循环遍历
因为数组是循环的,所以单纯遍历一次数组可能找不到所有元素的下一个更大值,特别是数组的前半部分的元素可能需要比较数组后半部分的元素。因此,可以通过遍历数组两次来解决这个问题,实质上是模拟了数组的循环。 -
使用取模操作处理索引
遍历两倍长度的数组并使用取模操作(i % size
),可以有效地模拟循环数组的行为,这样就可以保证每个元素都能被比较到。也可以避免数组下标越界~ -
栈的利用
- 当遍历到一个新元素时,如果它比栈顶元素索引对应的数组值大,说明找到了栈顶索引的下一个更大元素。
- 更新结果数组,将找到的更大元素赋值给对应的索引位置。
- 弹出栈顶元素(已经找到下一个更大值)。
- 将当前元素的索引压入栈中以供后续比较。
-
维护栈的单调性
保持栈的单调递减顺序(栈底到栈顶)。这样,当遇到一个较大的元素时,可以直接解决栈中所有比它小的元素的下一个更大元素问题。 -
最终结果的输出
遍历结束后,栈中可能还有一些元素,它们没有更大的元素,它们在结果数组中对应的值会是初始设置的-1
(如果未找到更大值)。遍历完两倍长度后,返回结果数组。
1.2、代码
class Solution {
public int[] nextGreaterElements(int[] nums) {
// 检查数组是否为空或长度不大于1,这种情况下无法找到任何元素的下一个更大元素
if(nums == null || nums.length <= 1) {
return new int[]{-1}; // 返回包含单个-1的数组,表示没有下一个更大元素
}
int size = nums.length; // 获取数组长度
int[] result = new int[size]; // 创建结果数组,用来存放每个元素的下一个更大元素
Arrays.fill(result, -1); // 默认填充为-1,表示如果没有找到更大的元素就保留这个值
Stack<Integer> st = new Stack<>(); // 创建一个栈,用于存放数组元素的索引
// 遍历数组两次,模拟循环数组的效果
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(); // 将栈顶元素弹出,因为我们已经找到了它的下一个更大元素
}
if (i < size) {
st.push(i); // 在第一轮遍历中,将每个元素的索引压入栈中
}
}
return result; // 返回包含下一个更大元素的结果数组
}
}
二、接雨水
42.原题链接
本题可以用双指针法和单调栈法解决。
2.1、双指针法
2.1.1、思路
-
初始化
定义两个指针left
和right
,分别指向数组的开始和结束。同时,定义两个变量maxLeft
和maxRight
,初始值设为数组两端的值。这两个变量用来跟踪到目前为止遇到的最高的左边和右边的柱子。 -
从两边向中心遍历
双指针法核心在于从两端向中间遍历,通过比较left
和right
两个指针所指向的柱子的高度,决定是移动left
指针还是right
指针。
- 如果
height[left] < height[right]
,则处理left
指针,因为此时左侧柱子较矮,决定了水的高度上限由左侧控制。 - 如果
height[right] <= height[left]
,则处理right
指针,因为此时右侧柱子较矮或者和左侧柱子相等,水的高度上限由右侧控制。
- 更新最大高度和计算积水
-
当移动
left
指针时:- 更新
maxLeft
为到目前为止遇到的最大左侧柱子高度。 - 计算当前位置可能的积水量,即
maxLeft - height[left]
,如果这个值为正,累加到总积水量中。 left
指针向中心移动。
- 更新
-
当移动
right
指针时:- 更新
maxRight
为到目前为止遇到的最大右侧柱子高度。 - 计算当前位置可能的积水量,即
maxRight - height[right]
,如果这个值为正,累加到总积水量中。 right
指针向中心移动。
- 更新
-
结束条件
当left
指针超过right
指针时,遍历结束。此时,所有可能的积水位置已经计算完成。 -
计算总积水量
遍历完成后,累计的积水量即为所有位置积水量之和。
这种方法的优势在于只需遍历一次数组,且不需要额外的空间(除了几个辅助变量外),从而使得时间复杂度为O(n),空间复杂度为O(1)。
2.1.2、代码
class Solution {
public int trap(int[] height) {
int length = height.length;
// 如果数组长度小于3,没有足够的柱子形成低洼地积水
if (length <= 2) return 0;
// maxLeft数组记录每个位置左侧的最大高度
int[] maxLeft = new int[length];
// maxRight数组记录每个位置右侧的最大高度
int[] maxRight = new int[length];
// 初始化maxLeft数组的第一个值为第一个柱子的高度
maxLeft[0] = height[0];
// 从左向右计算每个位置的左侧最大高度
for (int i = 1; i < length; i++) {
maxLeft[i] = Math.max(height[i], maxLeft[i-1]);
}
// 初始化maxRight数组的最后一个值为最后一个柱子的高度
maxRight[length - 1] = height[length - 1];
// 从右向左计算每个位置的右侧最大高度
for(int i = length - 2; i >= 0; i--) {
maxRight[i] = Math.max(height[i], maxRight[i+1]);
}
int sum = 0; // 用于累计所有位置的积水量
// 遍历每个位置,计算积水量
for (int i = 0; i < length; i++) {
// 当前位置的积水量由左右两侧最小的最大高度决定,减去当前高度
int count = Math.min(maxLeft[i], maxRight[i]) - height[i];
// 如果计算结果为正,说明有积水,累加到总量中
if (count > 0) sum += count;
}
return sum; // 返回计算得到的总积水量
}
}
2.2、单调栈法
2.2.1、思路
-
理解问题
这个问题涉及一个数组,数组的每个元素表示柱子的高度。需要计算在柱子间由于高度差产生的低洼地方能积累多少水。因此,核心问题是找到每个柱子左右两边比它高的柱子,以决定这个位置能积多少水。 -
使用栈来跟踪柱子的索引
使用栈来存储那些可能形成凹形结构的柱子的索引。栈的使用是因为它能够帮助我们保持一个正在处理的元素的顺序,这些元素可能会在之后形成容器的一部分。 -
迭代遍历数组
从数组的第一个元素开始,对每个元素执行以下操作:
- 如果当前柱子比栈顶柱子矮或相等,就把当前柱子的索引推入栈中。
- 如果当前柱子比栈顶柱子高,表明我们可能找到了一个凹槽的右边界,可以开始计算水量。
- 计算积水量
当找到一个可能的右边界时(当前柱子比栈顶柱子高):
- 将栈顶索引弹出,这代表低洼处(凹槽)的底部。
- 如果栈不为空,查看新的栈顶,这是凹槽的左边界。
- 使用左边界和当前索引(右边界),以及底部索引计算水的体积:
- 宽度为右边界和左边界之间的距离减一。
- 高度为左右边界的较小高度减去底部的高度。
- 体积即为宽度乘以高度(如果计算结果为正)。
- 继续弹出栈顶元素和计算,直到当前柱子不再比栈顶柱子高或栈为空。
-
重复过程
继续向右遍历直到数组结束,每个柱子都尝试进行上述判断和计算。 -
总结结果
最终,所有积水的体积加起来就是解决问题的答案。
2.2.2、代码
class Solution {
public int trap(int[] height) {
int size = height.length;
// 如果数组长度小于3,则不可能形成任何可以积水的凹槽
if (size <= 2) return 0;
Stack<Integer> stack = new Stack<Integer>();
// 初始时,将第一个元素索引压入栈
stack.push(0);
int sum = 0; // 用于累计所有的积水量
// 从第二个元素开始遍历数组
for (int index = 1; index < size; index++) {
// 检查栈顶元素与当前元素的关系
while (!stack.isEmpty() && height[index] > height[stack.peek()]) {
// 当前元素高于栈顶元素,可能形成一个凹槽
int mid = stack.pop(); // 弹出凹槽底部
// 确保栈不为空,以便我们有左边界
if (!stack.isEmpty()) {
int left = stack.peek(); // 获取凹槽左边界
// 计算可能的积水高度
int h = Math.min(height[left], height[index]) - height[mid];
// 计算宽度
int w = index - left - 1;
// 计算当前凹槽的积水量
int hold = h * w;
// 如果计算结果为正,则添加到总积水量
if (hold > 0) sum += hold;
}
}
// 若当前元素高度等于栈顶元素高度,则更新栈顶,保持最右的索引
if (!stack.isEmpty() && height[index] == height[stack.peek()]) {
stack.pop();
}
// 将当前索引压入栈中
stack.push(index);
}
// 返回计算得到的总积水量
return sum;
}
}
总结
1.感想
- 明天第60天了,一刷要结束了。
2.思维导图
本文思路引用自代码随想录,感谢代码随想录作者。