Leetcode.42.Trapping Rain Water

题目

给定一个数组, 数组构成一个柱状图, 在柱状图中最多可以装多少水, 即求柱状图中间的小方块面积.

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Input: [4,2,3]
Output: 1

解析

主要是理解题目, 转换求解过程. 简化题目后, 就是针对每个元素, 就每个元素左右的最大值, 在用左右最大值得最小值和当前值比较.

思路1

简单粗暴的循环.
时间复杂度O(n²)

int trap(vector<int> &vec) {
    int res = 0;
    for (int i = 0;i < vec.size(); i++) {
        // 找左右比自己高的
        int l = vec[i], r = vec[i];
        for (int j = i-1;j >= 0;j--) {
            if (vec[j] > l) {
                l = vec[j];
            }
        }
        for (int j = i+1;j < vec.size();j++) {
            if (vec[j] > r) {
                r = vec[j];
            }
        }
        int h = min(l, r) - vec[i];
        if (h > 0) res += h;
    }

    return res;
}

思路2

DP, 分别在左右设置一个动态规划数组.
时间复杂度(2n)

int trap(vector<int> &vec) {
    int n = (int)vec.size();
    int res = 0;
    vector<int> dpL(n+1, 0), dpR(n+1, 0);

    for (int i= 0; i < n-1; i++) {
         dpL[i+1] = max(dpL[i], vec[i]);;
         dpR[n-i-2] = max(dpR[n-i-1], vec[n-i-1]);
    }

   for (int i= 0; i < n; i++) {
        int h = min(dpL[i], dpR[i]) - vec[i];
        if (h > 0) {
            res += h;
        }
   }

    return res;
}

思路3

双指针, 左右分别设置一个指针向中间靠拢.
时间复杂度O(n)

int trap(vector<int> &vec) {
    int n = (int)vec.size();
    int res = 0;
    int l = 0, r = n - 1;
    int maxL = 0, maxR = 0;
    while(l < r) {
        if (vec[l] > vec[r]) {
            if (vec[r] > maxR) {
                maxR = vec[r];
            } else {
                res += maxR - vec[r];
            }
            r--;
        } else {
           if (vec[l] > maxL) {
                maxL = vec[l];
           } else {
                res += maxL - vec[l];
           }
           l++;
        }
    }
    return res;
}

思路4

栈, 需要重点掌握.是所有方法中效率最高的.
时间复杂度O(n)

int trap(vector<int> &vec) {
     int res = 0;
     stack<int> s;
     for(int i = 0; i < vec.size(); i++) {
         while (!s.empty() && vec[i] > vec[s.top()]) {
             int top = s.top();
             s.pop();
             if (s.empty()) break;

             int w = i - s.top() - 1;
             int h = min(vec[i], vec[s.top()]) - vec[top];
             res += w * h;
         }
         s.push(i);
     }
     return res;
 }

总结

主要是对题目的理解, 将问题简化为一个直观的数学问题.

学习栈的巧妙使用.