番禺网站开发,initial wordpress,全新网站开发,wordpress有赞支付宝原题链接#xff1a;
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 题面#xff1a; 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 示例 1#xff1a; 输入#xff1a…原题链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 题面 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 示例 1 输入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 输入height [4,2,0,3,2,5]
输出9提示 n height.length1 n 2 * 10^40 height[i] 10^5 解题思路
由木桶理论可知某一列的储水量与他左边最高的柱子和右边最高的柱子之间的较矮者有关为这一列高度和它的差值。在上一篇博客我们使用了DP方法维护了两个数组left和right空间复杂度为O(n)但实际上我们可以使用双指针法空间复杂度可以优化到O(1)。
设左指针left右指针right当left和right未相遇时维护leftMax和rightMax左指针left只从左往右右指针right只从右往左leftMax max(leftMax, height[left])rightMax max(rightMax, height[right])。
当leftMax rightMax时我们可以计算出left位置的储水量为leftMax - height[left]并将left右移一位
当leftMax rightMax时我们可以计算出right位置的储水量为rightMax - height[right]并将right左移一位
当leftMax rightMax时无论对left操作还是对right操作都是可以的。
当left和right相遇时就可以结束计算了。 代码CPP
class Solution {
public:/*双指针将空间复杂度从O(n)优化至O(1)*/int trap(vectorint height) {int n height.size();int left 0, right n - 1;int leftMax 0, rightMax 0, ans 0;while (left right) {leftMax max(leftMax, height[left]);rightMax max(rightMax, height[right]);if (leftMax rightMax) {ans leftMax - height[left];left;} else {ans rightMax - height[right];right--;}}return ans;}
};
