[C++] Optimize from O(n) space to O(1)
Intuition\n Describe your first thoughts on how to solve this problem. \n- My first thoughts are using a double-ended queue  to simulate the game and reducing t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- My first thoughts are using a double-ended queue  to simulate the game and reducing the time complexity with `k >= n`\n- But when we cannot find the winner in `n` rounds\n  - The maximum of the array will keep staying at index `0` of the array\n  - So the `arr[0]` is the winner forever\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- `arr0` is the current winner\n- `win_count` is the win count of `arr0`\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: from $$O(n)$$ to $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n## Double-Ended Queue\n```\nclass Solution {\npublic:\n    // time/space: O(n)/O(n)\n    int getWinner(vector<int>& arr, int k) {\n        int n = arr.size();\n        if (k >= n) return *max_element(arr.begin(), arr.end());\n        \n        deque<int> dq(arr.begin(), arr.end());\n        unordered_map<int, int> win_count;\n        while (true) {\n            int arr0 = dq.front(); dq.pop_front();\n            int arr1 = dq.front(); dq.pop_front();\n            int winner = max(arr0, arr1);\n            int loser = min(arr0, arr1);\n            if ((++win_count[winner]) == k) return winner;\n            dq.push_front(winner);\n            dq.push_back(loser);\n        }\n        return -1;\n    }\n};\n```\n\n## Without Queue\n```\nclass Solution {\npublic:\n    // time/space: O(n)/O(1)\n    int getWinner(vector<int>& arr, int k) {\n        int n = arr.size();\n        int arr0 = arr[0];\n        int win_count = 0;\n        for (int i = 1; i < n; i++) {\n            if (arr0 > arr[i]) {\n                win_count++;\n            }\n            else {\n                arr0 = arr[i];\n                win_count = 1;\n            }\n            if (win_count == k) return arr0;\n        }\n        return *max_element(arr.begin(), arr.end());\n    }\n};\n```
['Queue', 'Simulation', 'C++']