天津建设集团网站,做网站后台用什么语言,seo做的比较牛的公司,酒楼网站模板什么时候能用双指针#xff1f; #xff08;1#xff09;对撞指针#xff1a; ①两数和问题中可以使用双指针#xff0c;先将两数和升序排序#xff0c;可以发现规律#xff0c;如果当前两数和大于target#xff0c;则右指针向左走。 ②接雨水问题中#xff0c;左边最… 什么时候能用双指针 1对撞指针 ①两数和问题中可以使用双指针先将两数和升序排序可以发现规律如果当前两数和大于target则右指针向左走。 ②接雨水问题中左边最大 和 右边最大 可以通过双指针 双变量维护。 2快慢指针 ①比如找到链表的中点快指针一次走两步满指针一次走一步。 3滑动窗口 滑动窗口维护当前窗口内满足要求。而双指针可以在整个数组中考虑问题。 ①比如接雨水这里考虑窗口极限满足右边界大于等于左边界此时左边界移动。 一、从单个水柱本身考虑 下标为i的水柱能接的雨水取决于它左边最高的水柱 和 右边最高的水柱的最小值包括它本身。 为了理解这一性质我们可以这样想象取出左边最高和最边最高的水柱将其比作一个碗的边界。中间坑坑洼洼忽高忽低高低错落碗面中的一个点的能接水的最高高度是多少呢 就是碗边界的最小值-该点的高度。 因此从单个水柱考虑我们只需要能够求出这个问题即可。 一、动态规划 我们定义两个数组 left_max[i]表示从0~i 中 水柱高度的最大值 right_max[i] 表示从i~height.size()-1中水柱高度的最大值 class Solution {
public:int trap(vectorint height) {int nheight.size();vectorint left_max(n);vectorint right_max(n);left_max[0]height[0];right_max[n-1]height[n-1];//求出左边最大值for(int i1;in;i){left_max[i]max(left_max[i-1],height[i]);}//求出右边最大值for(int in-2;i0;--i){right_max[i]max(right_max[i1],height[i]);}long long ans0;for(int i0;in;i){ansmin(left_max[i],right_max[i])-height[i];}return ans;}
};
二、双指针
class Solution {
public:int trap(vectorint height) {int nheight.size();int left_maxheight[0];int right_maxheight[n-1];int left0;int rightn-1;long long ans0;while(leftright){left_maxmax(left_max,height[left]);right_maxmax(right_max,height[right]);if(left_maxright_max){//说明右边这个right柱子 取决于 其右边的最高高度。ansright_max-height[right];--right;}else{ansleft_max-height[left];left;}}return ans;}
};
二、从整体水柱考虑 从左向右依次看对于第一个水柱而言直到遇到一个比它高的水柱其中间的水柱都由第一个水柱的高度决定。一种特殊情况是最后一个找不到比它高的水柱此时对它我们从右往左看即可。左右对称 class Solution {
public:int trap(vectorint height) {int left0;//左边指向当前左柱子当左柱子低于右柱子时它已经不再能装水了 int right1;//右边往右一直寻找比左柱子高的 或 相等高度的柱子int sum0;while(rightheight.size()){if(height[right]height[left]){int tempheight[left];while(left!right){sumtemp-height[left];left;}}right;}if(left!height.size()-1){int endleft;leftheight.size()-1;rightleft-1;while(rightend){if(height[right]height[left]){int tempheight[left];while(left!right){sumtemp-height[left];--left;}}--right;}}return sum;}
};
