class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        // Sort the array in non-decreasing order

        // The majority element is guaranteed to be at the middle of the sorted array
        // due to the definition of majority element (appears more than n/2 times)
    }
};

class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target)
    {
        int left = 0, right = numbers.size() - 1;
        while (left < right)
        {
            if (numbers[left] + numbers[right] < target) ++left;
            else if (numbers[left] + numbers[right] > target) --right;
            else return vector<int>{left + 1, right + 1};
        }
        return vector<int>{-1, -1};
    }
};

class MinStack {
public:
    MinStack() {}

    void push(int val) {
        s1.push(val);
        if(s2.empty() || val <= s2.top()) {
            s2.push(val);
        }
    }

    void pop() {
        // 如果 s1.top() == 最小值的話
        if(s1.top() == s2.top()) {
            s2.pop();
        }
        s1.pop();
    }

    int top() {
        return s1.top();
    }

    int getMin() {
        return s2.top();
    }
private:
    // 用兩個 stack 存
    // s1 -> 一般的 stack
    // s2 -> 用來存最小值的 stack
    stack<int> s1;
    stack<int> s2;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

/*
 * @lc app=leetcode id=152 lang=cpp
 *
 * [152] Maximum Product Subarray
 *
 * https://leetcode.com/problems/maximum-product-subarray/description/
 *
 * algorithms
 * Medium (34.13%)
 * Likes:    19009
 * Dislikes: 763
 * Total Accepted:    1.5M
 * Total Submissions: 4.3M
 * Testcase Example:  '[2,3,-2,4]'
 *
 * Given an integer array nums, find a subarray that has the largest product,
 * and return the product.
 *
 * The test cases are generated so that the answer will fit in a 32-bit
 * integer.
 *
 *
 * Example 1:
 *
 *
 * Input: nums = [2,3,-2,4]
 * Output: 6
 * Explanation: [2,3] has the largest product 6.
 *
 *
 * Example 2:
 *
 *
 * Input: nums = [-2,0,-1]
 * Output: 0
 * Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
 *
 *
 *
 * Constraints:
 *
 *
 * 1 <= nums.length <= 2 * 10^4
 * -10 <= nums[i] <= 10
 * The product of any subarray of nums is guaranteed to fit in a 32-bit
 * integer.
 *
 *
 */

// @lc code=start
class Solution {
public:
    int maxProduct(vector<int>& nums)
    {
        int n = nums.size();

        int curMax = nums[0], curMin = nums[0];
        int res = curMax;

        for (int i = 1; i < n; i++)
        {
            int cur = nums[i];
            int tempMax = max({cur, curMax * cur, curMin * cur});

            curMin = min({cur, curMax * cur, curMin * cur});
            curMax = tempMax;
            res = max(curMax, res);
        }
        return res;
    }
};
// @lc code=end

class Solution {
public:
    string reverseWords(string s)
    {
        // Create a stringstream object to help with splitting the string
        // Clear the input string to reuse it for the result
        // Variable to store each word
        // Loop through each word separated by spaces in the stringstream
        while()
        {
            // Skip empty tokens (extra spaces)
            // If this is the first word added to the result string
                // Initialize the result string with the first word
                // For subsequent words
                // Prepend the word to the result string
        }
        // Return the result string with words reversed
    }
};

class Solution {
public:
    string reverseWords(string s)
    {
        stringstream ss(s);
        string token;
        s = "";
        while (ss >> token)
        {
            s = token + ' ' + s;
        }
        return s.substr(0, s.size() - 1);
    }
};

class Solution {
public:
    string reverseWords(string s)
    {
        stringstream ss(s);
        s = "";
        string token;
        while(is >> token)
        {
            s = (s.empty() ? token : token + " " + s);
        }
        return s;
    }
};

class Solution {
public:
    string reverseWords(string s)
    {
        stringstream ss(s);
        s = "";
        string token;
        while(getline(ss, token, ' '))
        {
            if(token.empty()) continue;
            if(s.empty())
            {
                s = token;
            }
            else
            {
                s = token + ' ' + s;
            }
        }
        return s;
    }
};

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto& token : tokens) {
            if(token != "+" && token != "-" && token != "*" && token != "/") {
                st.push(stoi(token));
            } else {
                int num1 = st.top(); st.pop();
                int num2 = st.top(); st.pop();
                if(token == "+") st.push(num2 + num1);
                if(token == "-") st.push(num2 + num1);
                if(token == "*") st.push(num2 * num1);
                if(token == "/") st.push(num2 / num1);
            }
        }
        return st.top();
    }
};

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        int n = points.size();

        // 保存經過相同直線的最多點的數量
        int maxSlope = 0;

        // 保存斜率與點個數的 mapping
        // {斜率: 通過的點個數}
        unordered_map<double, int> m;

        // 使用兩個迴圈走訪兩個 points
        for (int i = 0 ; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // point1(x1, y1)
                double x1 = points[j][0];
                double y1 = points[j][1];

                // point2(x2, y2)
                double x2 = points[i][0];
                double y2 = points[i][1];

                if(y2 == y1 && x2 == x1)
                {
                    // 如果兩個點重疊，則跳過這個點
                    continue;
                }
                else if (x2 == x1)
                {
                    // 如果兩個點在 x 軸上重合
                    // 斜率為 INT_MAX
                    m[INT_MAX]++;
                }
                else
                {
                    // 其他的狀況才可以套用斜率公式
                    double slope = (y2 - y1) / (x2 - x1);
                    // 對於相同的斜率，點的個數 + 1
                    m[slope]++;
                }
            }

            // 對於每個點，走訪 m 並找到最多點的斜率，並將其保存到 curMax 中。
            int curMax = 0;
            for (auto a : m)
            {
                curMax = max(curMax, a.second);
            }
            maxSlope = max(maxSlope, curMax);

            // 清空 hashMap，計算下一次的組合
            m.clear();
        }
        // 最後回傳 maxSlope + 1，因為需要考慮到自己本身
        return maxSlope + 1;
    }
};

struct Node {
    // Constructor to initialize a node with key and value
};

class LRUCache {
private:
    // Capacity of the cache

    // Hash map to store key to node mappings

    // Dummy head and tail nodes for the doubly linked list

    // Helper function to remove a node from the doubly linked list
    void remove()
    {
    }

    // Helper function to add a node to the end (before the tail) of the doubly linked list
    void add()
    {
    }

public:
    // Constructor to initialize the LRU Cache with given capacity
    LRUCache(int capacity)
    {
    }

    // Destructor to clean up all nodes
    ~LRUCache()
    {
    }

    // Function to get the value of a key
    int get(int key)
    {
        // If key is not found, return -1

        // Move the accessed node to the end (most recently used)

        // Return the value associated with the key
    }

    // Function to put a key-value pair in the cache
    void put(int key, int value)
    {
        // If key already exists, remove the existing node

        // Create a new node for the key-value pair

        // If the cache exceeds capacity, remove the least recently used (LRU) node
        if ()
        {
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

struct Node {
    int key;
    int val;
    Node* next;
    Node* prev;
    Node(int key, int val) : key(key), val(val), next(nullptr), prev(nullptr) {}
};

class LRUCache {
private:
    int cap;

    unordered_map<int, Node*> m;

    Node* head = new Node(-1, -1);
    Node* tail = new Node(-1, -1);

    // head <-> 1 <-> 2 <-> 3 <-> tail
    //                ^ node
    //          ^ prev_node
    //                      ^ next_node
    void remove(Node* node)
    {
        Node* prev_node = node->prev;
        Node* next_node = node->next;

        prev_node->next = next_node;
        next_node->prev = prev_node;
    }

    // head <-> 1 <-> 2 <-> tail
    //                ^ prev_node
    //                       ^ next_node
    void add(Node* node)
    {
        Node* prev_node = tail->prev;
        Node* next_node = tail;

        prev_node->next = node;
        next_node->prev = node;

        node->next = next_node;
        node->prev = prev_node;
    }

public:
    LRUCache(int capacity)
    {
        cap = capacity;
        // head <-> tail
        head->next = tail;
        tail->prev = head;
    }

    ~LRUCache()
    {
        Node* cur = head;
        while (cur) {
            Node* next = cur->next;
            delete cur;
            cur = next;
        }
    }

    int get(int key)
    {
        if(!m.count(key)) return -1;
        Node* node_to_get = m[key];
        remove(node_to_get);
        add(node_to_get);
        return node_to_get->val;
    }

    void put(int key, int value)
    {
        if(m.count(key)) remove(m[key]);

        Node* node_to_put = new Node(key, value);
        m[key] = node_to_put;
        add(node_to_put);

        if (m.size() > cap)
        {
            Node* node_to_delete = head->next;
            remove(node_to_delete);
            m.erase(node_to_delete->key);
            delete node_to_delete;
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector<int> res;
public:
    vector<int> postorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }
    void dfs(TreeNode* root) {
        if(!root) return;
        dfs(root->left);
        dfs(root->right);
        res.push_back(root->val);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(!root) return res;
        stack<TreeNode*> stk;
        stk.push(root);
        while (!stk.empty()) {
            TreeNode* node = stk.top(); stk.pop();
            res.push_back(node->val);
            if(node->left) {
                stk.push(node->left);
            }
            if(node->right) {
                stk.push(node->right);
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};