网站怎么做直播功能,公众号建网站,企业网站营销策划,wordpress首页文章显示缩略图目录题目思路暴力法动态规划双指针法单调栈题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出#xff1a;6 解释#xff1a;上面是由数组…
目录题目思路暴力法动态规划双指针法单调栈题目
给定 n 个非负整数表示每个宽度为 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.length 0 n 3 * 10^4 0 height[i] 10^5 思路
对于数组中的每个元素最高水位为两边最大高度的较小值 - 当前高度的值 用伪代码描述 water[i] min(left,right) - height[i]; 有一说一没想到是对每个元素进行计算的以为是找到几个较高点然后划分区间分别计算。 这样问题就可以化简为寻找每个元素右边最大的值和左边最大的值了。 没想到这个我感觉很难往下做下去。
暴力法
使用暴力法对于遍历数组的时候对应的元素找左右最大值,顺着上面的思路来一遍 显然时间复杂度是O(n^2)的
class Solution {
public:int trap(vectorint height){int ans 0;int n height.size();for(int i 0; i n; i){//找左右最大值int left_max 0, right_max 0;for(int j i; j 0; j--)left_max max(left_max,height[j]);for(int j i; j n; j)right_max max(right_max,height[j]);//累积此位置的雨水ans min(left_max,right_max) - height[i];}return ans;}
};动态规划
之前对于每个元素的左右最大值我们是在遍历该元素的时候找的。可以预先找到存储下来计算雨水的时候直接查询即可。 需要预先构造出两个数组用来存放。 填充极大值数组的时候要记住 从左向右遍历每次更新左极大值,当前元素的左极大值只和当前元素和左边一个元素的左极大值有关。 即left_max[i] max(height[i],left_max[i - 1]); 从右向左遍历每次更新右极大值,当前元素的右极大值只和当前元素和右边一个元素的右极大值有关 即:right_max[i] max(height[i],right_max[i 1]); 这个方法有两个细节 1、考虑输入数组为空 2、初始化左右极大值数组的第一个元素以及遍历的起点
显然时间复杂度是O(n)的。是遍历了3次原数组。
class Solution {
public:int trap(vectorint height){if(height.empty()) return 0;int ans 0;int n height.size();vectorint left_max(n);vectorint right_max(n);//初始化//第一个元素的左边没有元素所以左极大值就是本身left_max[0] height[0];//最后一个元素的右边没有元素所以右极大值就是本身right_max[n - 1] height[n - 1];//从左向右遍历每次更新左极大值,当前元素的左极大值只和当前元素和左边一个元素的左极大值有关for(int i 1; i n; i)left_max[i] max(height[i],left_max[i - 1]);//从右向左遍历每次更新右极大值,当前元素的右极大值只和当前元素和右边一个元素的右极大值有关for(int i n - 2; i 0; i--)right_max[i] max(height[i],right_max[i 1]);for(int i 0; i n; i){ans min(left_max[i],right_max[i]) -height[i];}return ans;}
};双指针法
动态规划是遍历了两次使用双指针可以实现只遍历一次就实现填充左右极大值数组。 感觉有个解释解释的非常好 https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/327718
1、明确变量意义 left_max左边的最大值它是从左往右遍历找到的 right_max右边的最大值它是从右往左遍历找到的 left从左往右处理的当前下标 right从右往左处理的当前下标 2、明确已知定理 定理一在某个位置i处它能存的水取决于它左右两边的最大值中较小的一个。 定理二当我们从左往右处理到left下标时左边的最大值left_max对它而言是可信的但right_max对它而言是不可信的。见下图由于中间状况未知对于left下标而言right_max未必就是它右边最大的值 定理三当我们从右往左处理到right下标时右边的最大值right_max对它而言是可信的但left_max对它而言是不可信的。 3、得到具体细节 对于位置left而言它左边最大值一定是left_max右边最大值“大于等于”right_max这时候如果left_maxright_max成立那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max都不影响这个结果。 所以当left_maxright_max时我们就希望去处理left下标反之我们希望去处理right下标。 4、知道了这些就可以写代码了
class Solution {
public:int trap(vectorint height){if(height.empty()) return 0;int ans 0;int n height.size();int left 0,right n - 1;int left_max height[left], right_max height[right];while(left right){if(left_max right_max){//还要判断left_max与当前的值谁大如果当前值大就不需要累积了。if(left_max height[left]) left_max height[left];else ans (left_max - height[left]);left;}else{//还要判断left_max与当前的值谁大如果当前值大就不需要累积了。if(right_max height[right]) right_max height[right];else ans (right_max - height[right]);right--;}}return ans;}
};单调栈
尽管之前写过接近8题的单调栈的题目这一题我使用单调栈的思路感觉并不是很清晰。而且粗略看了官方题解也没理解具体细节。 下面两个单调栈的讲法都比较好 我下面使用的图也是从这两个地方嫖的。 https://leetcode-cn.com/problems/trapping-rain-water/solution/42-jie-yu-shui-shuang-zhi-zhen-dong-tai-gui-hua-da/ https://leetcode-cn.com/problems/trapping-rain-water/solution/dan-diao-zhan-jie-jue-jie-yu-shui-wen-ti-by-sweeti/ 单调栈计算雨水的方式是按照行计算的 还有两个个需要注意的地方 1、我们构建的是单调递减栈一旦发现添加的柱子高度大于栈头元素了此时就出现凹槽了栈头元素就是凹槽底部的柱子栈头第二个元素就是凹槽左边的柱子而添加的元素就是凹槽右边的柱子。 如下图所示 2、遇到相同高度的柱子怎么办。 遇到相同的元素更新栈内下标就是将栈里元素旧下标弹出将新元素新下标加入栈中。 因为我们要求宽度的时候 如果遇到相同高度的柱子需要使用最右边的柱子来计算宽度。 接下来就可以套用模板写代码了 这里借鉴了代码随想录的冗余代码能够较好地理解for循环中三个情况具体处理。
class Solution {
public:int trap(vectorint height){if(height.empty()) return 0;int ans 0;int n height.size();vectorint st;for(int i 0; i n; i){//如果栈为空或者栈顶元素大于height[i]入栈if( st.empty() || height[i] height[st.back()]){st.emplace_back(i);}//如果栈不为空且栈顶元素height[i]更新栈顶元素取更右边的else if(!st.empty() height[i] height[st.back()]){st.pop_back();st.emplace_back(i);}//如果栈不为空且栈顶元素小于height[i]else{while(!st.empty() height[i] height[st.back()]){int mid st.back();st.pop_back();if(!st.empty()){int H min(height[st.back()],height[i]) - height[mid];int W i - st.back() -1; //i与st.back()之间的宽度ans H * W;}}st.emplace_back(i);}}return ans;}
};
