自己的暴力想法,把圖形看成一個個碗,一段一段地算,錯誤示例

class Solution {
public:int trap(vector<int>& height) {int s = height.size();int sum = 0,kk=1;int flag = 0;int p1 = -1, p2 = -1;for (int i = 1; i < s; i++) {cout<<p1<<endl;if (p1 >= 0 && flag) {if (height[i] >=height[p1]) // 找到了高于最左邊的值,短板效應,后面即便更大該曲線的水也不變{for (int j = p1 + 1; j < i; j++) {sum += height[p1] - height[j];}p1 = -1;flag = 0;kk=1;} else if (height[i] < height[i - 1]) // 該段最高點到了{for (int j = p1 + 1; j < i - 1; j++) {sum += height[i - 1] - height[j];}p1 = -1;flag = 0;kk=1;} else if (i == s - 1) //{for (int j = p1 + 1; j < i; j++) {sum += height[i] - height[j];}}if (p1 >= 0 && height[i] <= height[i - 1]) {p2 = i;} else if (p1 >= 0 && height[i] > height[i - 1]) {flag = 1;}if (height[i] < height[i - 1]&&kk) {p1 = i - 1;kk=0;}}return sum;}
};

主要問題在于,不好判斷一段盛水區間什么時候結束,蠢麻了,然后想到DP,前面錯誤想法的前提上肯定想不明白的

題解思路是這樣的,每一列盛水是由該列左右兩側最大值的較小值決定的,較小值減去該列值即為該列盛水量,所以建兩個數組,分別存左右最大,然后計算即可

class Solution {
public:int trap(vector<int>& height) {int s=height.size();int sum=0;int o=height[0],p=height[s-1];vector<int>kk;for(int i=0;i<s;i++){o=max(o,height[i]);kk.push_back(o);}for(int i=s-1;i>=0;i--){p=max(p,height[i]);kk[i]=min(kk[i],p);sum+=kk[i]-height[i];}return sum;}
};