I was fool...


  • -1
    X

    Here is my Time Limit Exceeded solution:

    int trap(vector<int>& height) {
        vector<std::tuple<unsigned, int>> points(height.size());
        for (auto i = 0u; i< height.size(); ++i) {
            points[i] = std::make_tuple(i, height[i]);
        }
        
        std::sort(height.begin(), height.end());
        height.erase(std::unique(height.begin(), height.end()), height.end());
        
        auto volume = 0;
        auto prevh = 0;
        for (auto i = 0u; i < height.size(); ++i) {
            auto h = height[i];
            auto it = std::remove_if(points.begin(), points.end(), [=](std::tuple<unsigned, int>& p) {
                return std::get<1>(p) < h;
            });
            points.erase(it, points.end());
            if (points.size() < 2)
                break;
            auto width = std::get<0>(points.back()) - 1 - std::get<0>(points.front()) - points.size() + 2;
            volume += width * (h - prevh);
            prevh = h;
        }
        return volume;
    }
    

  • 0

    @xpol Have no idea what you are trying to achieve here. The trapping array can be better handled, you are just perplexing the problem.


Log in to reply
 

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