# 2263. Make Array Non-decreasing or Non-increasing

• Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: int convertArray(vector& nums) { return min(cost(nums), cost(negative(nums))); } private: int cost(const vector& nums) { int ans = 0; priority_queue maxHeap; // Greedily make nums non-decreasing for (const int num : nums) { if (!maxHeap.empty() && maxHeap.top() > num) { ans += maxHeap.top() - num, maxHeap.pop(); maxHeap.push(num); } maxHeap.push(num); } return ans; } vector negative(const vector& nums) { vector A(nums); for (int& a : A) a *= -1; return A; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public int convertArray(int[] nums) { return Math.min(cost(nums), cost(negative(nums))); } private int cost(int[] nums) { int ans = 0; Queue maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); // Greedily make nums non-decreasing for (final int num : nums) { if (!maxHeap.isEmpty() && maxHeap.peek() > num) { ans += maxHeap.poll() - num; maxHeap.offer(num); } maxHeap.offer(num); } return ans; } private int[] negative(int[] nums) { int[] A = nums.clone(); for (int i = 0; i < A.length; ++i) A[i] *= -1; return A; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution: def convertArray(self, nums: List[int]) -> int: def cost(nums: List[int]) -> int: ans = 0 minHeap = [] # Greedily make nums non-increasing for num in nums: if minHeap and minHeap[0] < num: ans += num - heapq.heappushpop(minHeap, num) heapq.heappush(minHeap, num) return ans return min(cost(nums), cost([-num for num in nums]))