网站常识,seo推广方案,商城网站建设公司电话,唐山网页设计题目来源#xff1a;https://leetcode.cn/problems/trapping-rain-water/description/ C题解1#xff1a;双指针
按列算#xff0c;一列一列的求雨水面积。使用双指针是记录当前列左右侧的最大元素。 class Solution {
public:int trap(vectorint height) {in…题目来源https://leetcode.cn/problems/trapping-rain-water/description/ C题解1双指针
按列算一列一列的求雨水面积。使用双指针是记录当前列左右侧的最大元素。 class Solution {
public:int trap(vectorint height) {int result 0;int len height.size();vectorint leh(len, 0), rih(len, 0);leh[0] 0;rih[len-1] 0;for(int i 0; i len; i) {if(i 1 len) {leh[i1] max(leh[i], height[i]);}if(len-i-2 0){rih[len-i-2] max(rih[len-i-1], height[len-i-1]);}}for(int i 0; i len; i) {int tmp min(leh[i], rih[i]);if(tmp height[i]) result result tmp - height[i];}return result;}
};
C题解2单调栈注意栈存放元素索引就可以直接找到元素值
按行算横向算法。用单调栈可以求单前列右侧大的元素值。 当height[i]比st.top()所在元素值大时如果st弹出一个元素后不是空栈那么说明一定有凹槽能装雨水。因为栈里存放的是索引所以可以求出横向有多长即上面箭头的长度再比较一下height[i]与新的height[st.top()]的长短可以求出纵向有多长相乘即可求出箭头所在位置蓝色面积。
class Solution {
public:int trap(vectorint height) {int len height.size();if(len 2) return 0;stackint st;int result 0;for(int i 0; i len; i) {while(!st.empty() height[i] height[st.top()]) {int tmp st.top();st.pop();if(!st.empty()) {result (min(height[i], height[st.top()]) - height[tmp]) * (i - st.top() - 1);}}st.push(i);}return result;}
};
