Two Sweeps vs. Max Heap
Two Sweeps\nWe could use a heap and one sweep, but for O(n) solution we can just do two sweeps.\n\nC++\ncpp\nint sumOfBeauties(vector<int>& nums) {\n    int res
#### Two Sweeps\nWe could use a heap and one sweep, but for O(n) solution we can just do two sweeps.\n\n**C++**\n```cpp\nint sumOfBeauties(vector<int>& nums) {\n    int res = 0, maxj = nums[0], mink = nums.back();\n    vector<bool> b2(nums.size());\n    for (int i = 1; i < nums.size() - 1; maxj = max(maxj, nums[i++])) {\n        b2[i] = maxj < nums[i];\n        res += nums[i - 1] < nums[i] && nums[i] < nums[i + 1];\n    }\n    for (int i = nums.size() - 2; i > 0; mink = min(mink, nums[i--]))\n        res += b2[i] && nums[i] < mink;\n    return res;\n}\n```\n#### Max Heap\nIt may not be obvious why max heap works, but an example can help. Say we have `[7,1,2,3,4,5]`, and the initial heap state is `[7,3,2,1]`. After we check 7|3 < 4 < 5|5 (one point), we remove 7 (top of the head). Now we check 3|2 < 3 < 4|4 (also one point). Note that this works for a strict "less" comparison; it won\'t work for "less or equal".\n\n**C++**\n```cpp\nint sumOfBeauties(vector<int>& nums) {\n    int res = 0, mink = nums.back();\n    priority_queue<int> pq(begin(nums), prev(prev(end(nums))));\n    for (int i = nums.size() - 2; i > 0; --i) {\n        res += nums[i - 1] < nums[i] && nums[i] < nums[i + 1];\n        res += pq.top() < nums[i] && nums[i] < mink;\n        mink = min(mink, nums[i]);\n        pq.pop();\n    }\n    return res;\n}\n```
[]