Leetcode 42. Trapping Rain Water (cpp)

题目

解法1：暴力

这题关键在于，每个位置能盛放多少水由这个位置左边的最大值和右边的最大值中的最小值决定的。到每个位置也只需要计算当前位置能盛放多少水即可。知道了这点，剩下的就是怎么优化罢了，原理都一样

class Solution {
    
public:int trap(vector<int>& height) {
    int n=height.size();int ans = 0;for (int i=0;i<n;i++){
    int left_max = 0, right_max = 0;for (int j=i-1;j>=0;j--){
    left_max = max(left_max,height[j]);}for (int j=i+1;j<n;j++){
    right_max = max(right_max,height[j]);}if (min(left_max,right_max) - height[i] > 0){
    ans += min(left_max,right_max) - height[i]; }}return ans;}
};

解法2：动态规划

预存每个位置对应的left_max和right_max

class Solution {
    
public:int trap(vector<int>& height) {
    int n=height.size();vector<int> left_max(n,0);vector<int> right_max(n,0);int tmp = 0;for (int i=1;i<n;i++){
    tmp = max(tmp,height[i-1]);left_max[i] = tmp;}tmp = 0;for (int i=n-2;i>=0;i--){
    tmp = max(tmp,height[i+1]);right_max[i] = tmp;}int ans = 0;for (int i=0;i<n;i++){
    if (min(left_max[i],right_max[i])-height[i]>0){
    ans += min(left_max[i],right_max[i])-height[i];}}return ans;}
};

解法3：stack

class Solution {
    
public:int trap(vector<int>& height) {
    int ans = 0, current = 0;stack<int> st;while (current < height.size()){
    while (!st.empty() && height[current]>height[st.top()]){
    int top = st.top();st.pop();if (st.empty()) break;int dis = current - st.top() - 1;int bound_height = min(height[current],height[st.top()]) - height[top];ans += dis * bound_height;}st.push(current++);}return ans;}
};

解法4：two pointers

class Solution {
    
public:int trap(vector<int>& height) {
    int ans = 0, left = 0, right = height.size() - 1;int left_max = 0, right_max = 0;while (left < right){
    if (height[left] < height[right]){
    height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);left += 1;}else {
    height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);right -= 1;}}return ans;}
};