C++ 接雨水，不看后悔系列,解一道高频面试题

素颜马尾好姑娘i 2023-02-13 11:26 6阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bGVpZG5m_size_16_color_FFFFFF_t_70]  
这是一道同事讨论过的一道趣味题，综合了比较多的解题思想，其中有二分，递归，分治等思想。闲来抽空实现了下，如有错误请多多指出,或者有优化处请多多指出。逻辑不是很复杂，直接上代码吧。

//
    // main.cpp
    // 面试题经典
    //
    // Created by 于磊 on 2020/5/27.
    // Copyright © 2020 于磊. All rights reserved.
    //
    
    #include <iostream>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    typedef vector<int>::const_iterator c_iter;
    int Area = 0;
    
    size_t Max(c_iter begin,c_iter end,const vector<int> water){ 
        return *max_element(begin, end);
    }
    size_t MaxIndex(c_iter begin,c_iter end,const vector<int> water){ 
        return max_element(begin,end) - begin;
    }
    
    int getAreaL(c_iter _begin,c_iter _end,const vector<int> _water ){ 
        if (_begin == _end) { 
            return 0;
        }
        size_t _idx = MaxIndex(_begin, _end,_water);
        size_t _max = Max(_begin, _end,_water);
        if (_idx>0) { 
            getAreaL(_begin, _begin +_idx, _water);
        }
        while (_begin+_idx!=_end) { 
            Area+=_max-*(_begin++ +_idx);
        }
        return 0;
    }
    
    int getAreaR(c_iter _begin,c_iter _end,const vector<int> _water ){ 
        if ( _begin-1 == _end ) { 
            return 0;
        }
        size_t _idx = MaxIndex(_begin, _end,_water);
        size_t _max = Max(_begin, _end,_water);
        auto maxIdx =_begin+_idx+1;
        if ( _idx<_end-_begin-1) { 
            getAreaR(maxIdx, _end, _water);
        }
        
        while (_begin!=maxIdx) { 
            Area+=_max-*(_begin++);
        }
        return 0;
    }
    
    int main(int argc, const char * argv[]) { 
        vector<int> water;
        int i;
        std::cout << "please input number of water container end of by #\n";
        while (cin >> i && i != '#') { 
            water.push_back(i);
        }
        size_t _idx = MaxIndex(water.begin(), water.end(),water);
        getAreaL(water.begin(), water.begin()+_idx, water);
        getAreaR(water.begin()+_idx, water.end(), water);
        cout<<"总共装水 "<<Area<<endl;
        return 0;
    }

![在这里插入图片描述][20200528201534357.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bGVpZG5m_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200528195924111.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1bGVpZG5m,size_16,color_FFFFFF,t_70
[20200528201534357.png]: https://img-blog.csdnimg.cn/20200528201534357.png