True O(N) in C++, better than O(N log N)
By definition the Fibonacci sequence is an integer sequence that has no triplets making up a triangle of a non-zero area (triangle-triplets), as each number is 
By definition the Fibonacci sequence is an integer sequence that has no triplets making up a triangle of a non-zero area (triangle-triplets), as each number is the sum of the two preceding numbers:\n\n```\n1 1 2 3 5 8 13 ...\n```\n\nFor a given length `n`, among all sorted sequences of natural numbers with no triangle-triplets, the Fibonacci sequence is the sequence with the smallest number `a[i]` for `0 <= i < n`. In other words, it\'s the lexicographically smallest sequence of numbers without triangle-triplets.\n\nKnowing the maximum possible number `x` in the array (1\'000\'000 for this problem), we can find the length `K` of the longest sequence that has no triangle-triplets using the next formula (or alternatively with the familiar Fibonacci number iterative algorithm):\n\n```\nK = ceil(log(x * sqrt(5) - .5) / log(1.618))\n```\n\nIf a sequence of numbers with a maximum element `x` has more than `K` elements, then it   contains triangle-triplets.\n\nNow I state that if there are no triangle-triplets in the top-K elements of an array of numbers, then there are no triangle-triplets in the whole array. To find the largest perimeter triangle we only need to consider the top-K elements of the array of numbers.\n\n```\nclass Solution {\npublic:\n    int largestPerimeter(vector<int>& nums) {\n    https://leetcode.com/qyryq/\n        int k = min(invfib(1\'000\'000), nums.size());\n        priority_queue<int, vector<int>, greater<>> q;\n        for (auto n : nums)\n            if (q.size() < k || n >= q.top()) {\n                q.push(n);\n                if (q.size() > k) q.pop();\n            }\n        vector<int> v;\n        for (; !q.empty(); q.pop())\n            v.emplace_back(q.top());\n        for (size_t i = k-3; i < k; i--)\n            if (v[i]+v[i+1] > v[i+2])\n                return v[i]+v[i+1]+v[i+2];\n        return 0;\n    }\nprivate:\n    size_t invfib(size_t x) const {\n        // https://stackoverflow.com/a/5162856/\n        // https://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_golden_ratio\n        return ceil(log(x * sqrt(5) - .5) / log(1.618));\n    }\n};\n```\n\nThe complexity of the algorithm is O(N * log( invfib(M) )), where N is the length of the `nums` vector and M is the maximum possible number in the vector. As M is fixed in this problem, we may consider the complexity of this algorithm to be O(N).\n\nOn large arrays the next approach is almost twice as fast as the priority queue one:\n\n```\nclass Solution {\npublic:\n    int largestPerimeter(vector<int>& nums) {\n    https://leetcode.com/qyryq/\n        const size_t k = 32ul;\n        size_t imin = 0;\n        vector<int> q(k, 0);\n        for (const auto& n : nums)\n            if (n > q[imin]) {\n                q[imin] = n;\n                imin = distance(begin(q), min_element(begin(q), end(q)));\n            }\n        sort(begin(q), end(q), greater{});\n        for (size_t i = 0; i < k-2; i++)\n            if (q[i] < q[i+1] + q[i+2])\n                return q[i]+q[i+1]+q[i+2];\n        return 0;\n    }\n};\n```\n\nHere I use `32ul` constant instead of calling `invfib` function, but it\'s not what makes the code faster. What does make it faster is the simplified loop body, that finds the smallest element in the `q` vector that holds the top-K elements. Asymptotically it should take more time that the priority queue approach, but I suppose the streamlined code is more "comfortable" for the modern CPU architecture to execute.
['C', 'Heap (Priority Queue)']