Description

Submission

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() < 2) return 0;
        int max_index = 0;
        for(int i = 0; i < height.size(); ++i) {
            if(height[max_index] < height[i]) max_index = i;
        }
        int left = 0;
        int area = 0;
        for(int i = 0; i < max_index; ++i) {
            if(height[i] > height[left]) {
                left = i;
            } else {
                area += (height[left] - height[i]);
            }
        }
        int right = height.size() - 1;
        for(int i = height.size() - 1; i > max_index; --i) {
            if(height[i] > height[right]) {
                right = i;
            } else {
                area += (height[right] - height[i]);
            }
        }
        return area;
    }
};

Submission 210308

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.empty()) return 0;
        
        vector<pair<int, int>> lStack, rStack;
        int n = height.size();
        
        for(int i = 0; i < n; ++i) {
            if(lStack.empty()) {
                lStack.push_back({height[i], i});
            } else if(lStack.back().first < height[i]) lStack.push_back({height[i] ,i});
            
            
            int j = n - 1 - i;
            if(rStack.empty()) {
                rStack.push_back({height[j], j});
            } else if (rStack.back().first < height[j]) rStack.push_back({height[j], j});
        }
        
        // left
        int ret = 0;
        for(int i = 0; lStack.size() > 1 && i < lStack.size() - 1; ++i) {
            int h = lStack[i].first;
            int beg = lStack[i].second + 1;
            int end = lStack[i+1].second;
            
            for(int j = beg; j < end; ++j) {
                ret += h - height[j];
            }
        }
        
        // right
        for(int i = 0; rStack.size() > 1 && i < rStack.size() - 1; ++i) {
            int h = rStack[i].first;
            int beg = rStack[i].second;
            int end = rStack[i+1].second;
            for(int j = beg; j > end; --j) {
                ret += h - height[j];
            }
        }
        
        // middle if possibly
        if(rStack.back().second != lStack.back().second) {
            int h = rStack.back().first;
            int beg = lStack.back().second + 1;
            int end = rStack.back().second;
            
            for(int j = beg; j < end; ++j) {
                ret += h - height[j];
            }
            
        }
        
        return ret;
        
    }
};