ConstructArray
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe problem asks you to generate a list of n distinct integers, ranging from 1 to n, 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe problem asks you to generate a list of n distinct integers, ranging from 1 to n, such that the list of absolute differences between consecutive elements contains exactly k distinct values.\n\nKey Points:\nYou have n numbers from 1 to n.\nYou need to arrange these numbers such that the list of consecutive differences has exactly k distinct integers.\nThe problem allows for multiple valid solutions, and any one of them is acceptable.\nPattern Recognition and Approach\nTo solve this problem, we can observe the following:\n\nMaximum Distinct Differences:\n\nThe maximum number of distinct absolute differences you can have in a list of length n is n-1. This occurs when each consecutive number differs from the previous by a unique value.\nFor example, the list [1, 2, 3, 4, 5] has differences [1, 1, 1, 1] (all the same), while the list [1, n, 2, n-1, 3, ...] alternates between large and small numbers, maximizing the distinct differences.\nMinimum Distinct Differences:\n\nThe minimum number of distinct absolute differences is 1, which occurs when the sequence is strictly increasing or decreasing, e.g., [1, 2, 3, 4, ...] with all differences being 1.\nStrategy:\n\nTo get exactly k distinct differences, start by creating the first k differences to be as distinct as possible, and then fill the rest of the sequence with a simple increasing sequence to ensure the remaining differences are the same.\nImplementation Strategy:\nGenerate Distinct Differences:\n\nAlternate between the smallest and largest remaining numbers to maximize the difference.\nStart with a sequence like [1, n, 2, n-1, 3, ...] until you have k distinct differences.\nFill the Rest:\n\nAfter achieving k distinct differences, fill the remainder of the list with a simple sequence to maintain the same difference.\n\n\n>\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> O(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ --> O(n)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> constructArray(int n, int k) {\n        vector<int> result;\n        int left = 1, right = n;\n\n        // Construct the first part of the array with k distinct differences\n        for (int i = 0; i < k; ++i) {\n            if (i % 2 == 0) {\n                result.push_back(left++);  // Pick from the start of the range\n            } else {\n                result.push_back(right--);  // Pick from the end of the range\n            }\n        }\n\n        // Fill the remaining part with a simple increasing sequence\n        if (k % 2 == 0) {\n            for (int i = right; i >= left; --i) {\n                result.push_back(i);\n            }\n        } else {\n            for (int i = left; i <= right; ++i) {\n                result.push_back(i);\n            }\n        }\n\n        return result;\n    }\n};\n\n\n\n```
['C++']