C++ NlogN easy-to-understand solution using scanning line method


  • 0
    N
    class Solution {
    public:
        int maxArea(vector<int>& height) {
            map< int, vector< list<int>::iterator > > heightMap;
            list<int> pos;
            for (int i = 0; i < height.size(); ++i) {
                heightMap[height[i]].push_back(pos.insert(pos.end(), i));
            }
            int sq = 0;
            for (auto& p : heightMap) {
                for (auto& it : p.second) {
                    sq = max(sq, p.first * max((pos.back() - *it), (*it - pos.front())));
                }
                for (auto& it : p.second) {
                    pos.erase(it);
                }
            }
            return sq;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.