网站开发与维护,服装公司发展规划,江西南昌网站制作,wordpress广告插件汉化题目描述#xff1a;
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
题目解答#xff1a;
class Solution {public int trap(int[] height) {int n height.length;int ans 0;if (n 3)return…题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
题目解答
class Solution {public int trap(int[] height) {int n height.length;int ans 0;if (n 3)return ans;int left 0, right n - 1;int maxl 0, maxr 0;while (left right) {maxl Math.max(maxl, height[left]);maxr Math.max(maxr, height[right]);ans maxl maxr ? maxl - height[left] : maxr - height[right--];}return ans;}
}题目思路
双指针法在这段代码中的思想是通过两个指针分别从数组的两端向中间移动同时维护左侧和右侧的最大高度。这种方法可以有效地减少计算量因为在移动过程中我们只关心较小的一侧的最大高度来计算雨水量。 初始化 初始化两个指针 left 和 right 分别指向数组的开头和末尾。初始化两个变量 maxl 和 maxr 分别表示左侧和右侧的最大高度初始值为 0。 int left 0, right n - 1;
int maxl 0, maxr 0;移动指针 在循环中通过比较 maxl 和 maxr 的大小选择较小的一侧。如果 maxl 小于 maxr说明左侧最高柱子决定了当前位置的雨水高度因此计算当前位置的雨水量并将结果累加到 ans 中。根据选择的最小高度移动对应的指针向中间靠拢。 while (left right) {maxl Math.max(maxl, height[left]);maxr Math.max(maxr, height[right]);ans maxl maxr ? maxl - height[left] : maxr - height[right--];
}核心思想 在每一步中都选择较小的一侧这样可以确保当前位置的雨水量是由较小的一侧的最大高度决定的。移动指针时总是移动较小一侧的指针这样可以确保在移动的过程中雨水的计算仍然是以较小的一侧为基准。
通过这种双指针的思想代码在一次遍历中完成了整个计算过程而不需要额外的空间从而实现了较好的时间复杂度。这种方法的关键在于巧妙地使用两个指针来同时遍历数组减少了不必要的计算提高了算法的效率。
其中使用了条件运算符三元运算符其形式为
//result condition ? expression_if_true : expression_if_false;
ans maxl maxr ? maxl - height[left] : maxr - height[right--];我们可以拆解它的含义
maxl maxr 表示当前左侧的最大高度小于右侧的最大高度。如果条件成立true则选择 maxl - height[left]表示当前位置的雨水量是由左侧的最大高度决定的然后将 left 指针向右移动。如果条件不成立false则选择 maxr - height[right--]表示当前位置的雨水量是由右侧的最大高度决定的然后将 right 指针向左移动。
整体来看这行代码实现了双指针移动的逻辑根据左右两侧的最大高度之间的关系来决定当前位置的雨水量。选择较小的一侧作为决定因素计算雨水量然后移动相应的指针使问题规模减小最终完成整个遍历过程。
这种表达方式是为了避免使用额外的 if-else 语句通过条件运算符直接在一行中完成逻辑。这样的写法简洁而清晰同时保持了代码的可读性。
